leetcode:167. Two Sum II - Input array is sorted

2023-05-16

目录

题目描述

实现

1.哈希表

2.二分查找法

3.双指针法


题目描述

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

  • Your returned answers (both index1 and index2) are not zero-based.
  • You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

实现

1.哈希表

       与第1题相同,也可以用哈希表存储numbers的值和索引,但是这样没有利用到numbers是个有序表的性质。时间复杂度是O(n),空间复杂度是O(n)。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0;i < numbers.length;i++) {
            int x = target-numbers[i];
            if(map.containsKey(x))
                return new int[]{map.get(x)+1,i+1};
            else {
                map.put(numbers[i],i);
            }
        }
        throw new IllegalArgumentException("no res");
    }
}

2.二分查找法

        二分查找用于在一个有序表A中查找值key,返回其对应的索引。设定两个指针i,j分别指向表头、表尾,计算得到M = (i+j)/2,判断M指向的元素与要查找的key大小,如果A[M] < key,则i=M+1,否则j=M,当i<j时循环,最后当i==j且A[i]==key时得到索引i返回,否则查找失败,表中不存在key,返回-1。在twosum中二分查找用于找target-numbers[i]在numbers中的位置,如果有则返回numbers当前索引和二分查找返回值。此算法时间复杂度为O(nlogn),空间复杂度为O(1),相比哈希法在空间开销上有所降低。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for(int i = 0;i < numbers.length;i++) {
            int x = target-numbers[i];
            int loc = bsearch(numbers, x, i+1);
            if( loc != -1) {
                return new int[] {i+1,loc+1};
            }
        }
        throw new IllegalArgumentException("no answer");
    }
    
    private int bsearch(int[] numbers, int key, int start) {
        int L = start;
        int R = numbers.length -1;
        while(L < R) {
            int M = (L+R)/2;
            if( numbers[M]<key ) {
                L = M+1;
            }
            else {
                R = M;
            }
        }
        return ((L == R && numbers[R] == key) ? R : -1);
        
    }
}

3.双指针法

       思路:target由数组中的两个数相加得到,两数相加只有三种可能,大于、小于、等于target。由于numbers是有序表,可以很方便调整相加的两数大小,于是可以设定两个指针,一个i指向数组numbers的头元素,另一个j指向尾元素,计算两数之和sum,如果sum > target,则说明需要一个更小的数与numbers[i]相加,如果sum < target,则说明需要一个更大的数与numbers[j]相加,在i<j时循环,直到sum == target。这个算法的时间复杂度是O(n),空间复杂度是O(1),比二分查找法在时间上更优。

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int start = 0;
        int end = numbers.length -1;
        while( start < end ) {
            if( numbers[start] + numbers[end] < target )
                start++;
            else if( numbers[start] + numbers[end] > target )
                end--;
            else
                return new int[] { start+1, end+1 };
        }
        throw new IllegalArgumentException("no answer");
    }
    
}

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

leetcode:167. Two Sum II - Input array is sorted 的相关文章

  • 如何使用 jQuery 清空输入字段

    我在移动应用程序中 使用输入字段来命令用户提交号码 当我返回并返回到输入字段显示输入字段中显示的最新数字输入的页面时 有没有办法在每次加载页面时清除该字段 shares keyup function payment 0 calcTotal
  • 读取以空格分隔的输入数字

    这可能是一个完全初学者的问题 但我还没有找到适合我的答案 目前 我正在为一个类编写一个程序 它接受用户的输入 可以是一个或多个用空格分隔的数字 然后确定该数字是否是质数 完全数或都不是 如果数字是完美的 那么它将显示除数 到目前为止 我已经
  • 每个日期的 SQL 总金额

    我有一个名为 rentals 的表 其中存储如下数据 id rent id start date end date amount 1 54 12 10 2019 26 10 2019 100 2 54 13 10 2019 20 10 20
  • pandas 中的 .sum() 方法给出不一致的结果

    我有一个大的 DataFrame 大约 4e 07 行 总结时 我得到2 显着不同的结果我是否做总和之前或之后列选择 另外 类型变化从 float32 到 float64 即使总数均低于 2 31 df col1 col2 col3 sum
  • PostgreSQL XPath 中是否实现了 XPath sum 或 fn:sum 函数?

    我正在使用 PostgreSQL 8 4XPath XML 函数 特征 这是文档中找到的改编示例 SELECT xpath my a value gt 15
  • MATLAB中对矩阵元素求和的方法有哪些?

    给定矩阵 A 1 2 3 4 5 6 7 8 9 如何使用 for 循环来计算矩阵中元素的总和 使用该函数编写一行 MATLAB 命令sum求和 矩阵元素在A 我的答案 1 for j 1 3 for i j 3 A i A i A j 1
  • React - 通过单击提交按钮将项目从输入添加到列表中

    我正在练习反应 并尝试通过单击提交按钮将项目添加到输入列表中 我更喜欢使用 state 和 setState 我很想得到一些帮助 我认为不需要我的代码 但无论如何这是它 class App extends Component state u
  • 使用CSS检测输入中是否有文本——在我正在访问且无法控制的页面上?

    有没有办法通过 CSS 检测输入中是否有文本 我尝试过使用 empty伪类 我尝试过使用 value 这两个都不起作用 我似乎无法找到单一的解决方案 我想这一定是可能的 考虑到我们有伪类 checked and indeterminate
  • 如何更改禁用输入的字体颜色?

    我需要更改 CSS 中禁用的输入元素的样式
  • 嵌套文档 MongoDB 中的求和

    我试图对一系列文档中的一些值求和 但没有成功 这是文件 db Cuentas find pretty Agno 2013 Egresos Fecha 28 01 2013 Monto 150000 Detalle Pago Nokia Lu
  • C# 控制台应用程序 - 如何始终从控制台读取输入?

    我目前正在编写一个使用大量多线程的控制台应用程序 我希望能够始终允许用户在控制台中输入内容 但是 线程会定期输出到控制台 但我希望用户始终能够在控制台中输入内容 并由我来处理输入 我将如何实现这一目标 我在网上没有找到任何相关内容 先谢谢了
  • 从外部文件获取输入?

    我需要从 C 的外部文件中获取非常基本的输入 我尝试在互联网上搜索几次 但没有任何内容真正适合我的需要 这将是一个输入来自的 txt 文件 其中将填充如下行 131 241 371 481 我已经有代码可以手动获取此输入 它看起来像这样 u
  • Onload 使输入大小适合文本长度

    我试图让 jQuery 测试 onLoad 输入框中文本的长度 并更改输入框的大小以适应 这是迄今为止我的代码尝试 emailSubject attr size this val length 我收到以下错误 this val 不是函数 我
  • Python对二维列表中具有相同第一个值的元素求和

    我正在尝试找到一种有效的方法来执行以下操作 我有这个样本 sample no 2 6 ja 5 7 no 4 9 ja 10 11 ap 7 12 并且需要 res no 6 15 ja 15 18 ap 7 12 即对第一个元素相同的子列
  • CSS/HTML:在输入字段周围创建发光边框

    我想为我的表单创建一些像样的输入 并且我真的很想知道 TWITTER 如何在输入周围制作发光边框 Twitter 边框示例 图片 我也不太知道如何创建圆角 干得好 glowing border border 2px solid dadada
  • C++ 中获取用户输入未执行/跳过的代码

    在下面的代码中 当我尝试让用户输入他们的名字时遇到错误 我的程序只是跳过它并直接进行函数调用 而不允许用户输入他们的名字 尽管出现错误 我的程序仍在编译 我不确定出了什么问题 因为我是根据在这里找到的其他示例编写该部分的 有什么建议么 in
  • ui内的输入组件:repeat,如何保存提交的值

    我正在显示数据库中的问题列表 对于每个问题 我必须显示选项列表 在本例中为单选按钮
  • 每次使用 JQuery 在输入字段中更改内容时如何执行函数?

    我有一个文本字段
  • JQuery 对话框作为输入

    我不太习惯使用 jquery 对话框之类的东西 所以这是一个新手问题 此时 我正在使用提示来获取 SharePoint 中用户的回复 var answer dialog Type the text you want to display i
  • 在 Python 上分析字符串输入直到达到某个字母

    我需要帮助来尝试编写程序的某个部分 这个想法是 一个人输入一堆乱码 程序会读取它 直到它到达 感叹号 例如 input Type something 人物类型 wolfdo65gtornado salmontiger223 如果我要求程序打

随机推荐