LeetCode 167：两数之和 II (有序数组)

小半 • 2023年2月3日上午10:54 • 技术随笔 • 阅读 213

思路：

①确定一个数nums[i] ②找另一个数target-nums[i]

方法一：二分查找

数组升序排列是使用二分查找的前提！
用for遍历数组每个数num[i]，
每一轮使用二分查找找是否存在 target-numbers[i]的数
注意for中i还是从0开始，数组索引从1开始，但是0依然存在
由于数组索引从1开始算，所以二分查找中left =i+1 ，每查完一个nums[i]，待查元素num[I]依次减少
注意返回的是 i+1, mid+1

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for(int i=0;i<numbers.length;i++){

            // 二分法， 由nums[i]， 找是否存在 val=target-nums[i]
            int val=target-numbers[i]; // 二分法需要找的值 ！
            int left=i+1; // 索引从1开始
            int right=numbers.length-1;
            while(left<=right){   // 注意是left<=right ！ left>right才跳出while
                int mid=left+(right-left)/2;
                if(numbers[mid]==val){
                    return new int[]{i+1,mid+1};
                }else if(val>numbers[mid]){
                    left=mid+1;
                }else if(val<numbers[mid]){
                    right=mid-1;
                }
            }
        }
        return new int[]{0,0};
    }
}

注意：循环判断条件是 while(left <= right)

时间复杂度：O(nlogn)，其中 n 是数组的长度。需要遍历数组一次确定第一个数，时间复杂度是 O(n)O(n)，寻找第二个数使用二分查找，时间复杂度是 O(logn)，因此总时间复杂度是 O(nlogn)。

空间复杂度：O(1)O(1)。

方法二：双指针 √

只要数组有序，就应该想到双指针技巧。这道题的解法有点类似二分查找，通过调节 left 和 right 就可以调整搜索范围

class Solution {
    public int[] twoSum(int[] numbers, int target) {
    // 双指针 相向而行
        int left=0;
        int right=numbers.length-1;
        while(left<right){
            int sum=numbers[left]+numbers[right];
            if(sum>target){
                right--;
            }else if(sum<target){
                left++;
            }else if(sum==target){
                return new int[]{left+1,right+1}; // 下标1开始，要+1
            }
        }
        return new int[0];
    }
}