【算法】Two Sum II - Input Array Is Sorted 两数之和 II

这篇具有很好参考价值的文章主要介绍了【算法】Two Sum II - Input Array Is Sorted 两数之和 II - 输入有序数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Two Sum II - Input Array Is Sorted 两数之和 II - 输入有序数组

问题描述：

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

$2 <= numbers.length <= 3 * 10^4\\ -1000 <= numbers[i] <= 1000\\ numbers 按非递减顺序排列\\ -1000 <= target <= 1000\\ 仅存在一个有效答案$

分析

第一个应该想到的就是暴力，时间复杂度 $O(N^2)$ .

暴力虽然时间复杂度高，但是绝对可以拿捏，不需要考虑其他特殊情况。

改进：

因为原数组是一个规律的有序数组，所以在找另一个数的时候，就可以二分了。时间复杂度 $O (N L o g N)$ .

特点：比较快，但是场景有限制，对编码能力有一定门槛。

再改进：

双指针，该方法还是基于有序数组，

从2个端点开始找，
如果 $s u m == t a r g e t$ ,说明找到了一个合法的pair。
否则 $s u m > t a r g e t$ ,那就需要把右端点像左移。
如果 $s u m < t a r g e t$ ,那就需要把左端点向右移。

特点：这个比二分更快，时间复杂度 $O (N)$ ,也是对场景有限制。

Two Sum 虽然简单，但是变种太多。如果不是有序的数组，这个时候，就不能直接使用二分和双指针了。

代码

二分

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        for(int i = 0;i<n; i++){
            int idx = find(numbers,i+1,n-1,target-numbers[i]);
            if(idx!=-1){
                return new int[]{i+1,idx+1};
            }
        }
        return new int[0];
    }

    public int find(int[] arr,int l,int r,int tar){
        int mid = 0;
        while(l<=r){
            mid = l+ (r-l)/2;
            if(arr[mid]== tar) return mid;
            if(arr[mid]>tar) r = mid-1;
            else l = mid+1;
        }        
        return -1;
    }
}

时间复杂度 $O(N\log N)$

空间复杂度 $O (1)$

双指针

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int l=0,r = numbers.length-1;
        while(l<r){
            int x = numbers[l]+numbers[r];
            if(x== target){
                return new int[]{l+1,r+1};
            }
            if(x>target) r--;
            else l++;
        }
        return new int[0];
    }
}