0%

leetcode每日一题-两数之和II-输入有序数组

Posted on Edited on In ,

两数之和II-输入有序数组

方法一：双指针

左指针$left$指向数组起始位置，右指针$right$指向数组结束位置。如果$nums[left]+nums[right]==target$，那么就结束。如果$nums[left]+nums[right]>target$，那么将右指针左移，如果$nums[left]+nums[right]<target$，那么将左指针右移。

1
class Solution {
2
    public int[] twoSum(int[] numbers, int target) {
3
        int[] ans = new int[2];
4
        int index1 = 0;
5
        int index2 = numbers.length-1;
6
        while(index1 < index2){
7
            if(numbers[index1]+numbers[index2] == target){
8
                break;
9
            }else if(numbers[index1]+numbers[index2]>target){
10
                index2--;
11
            }else if(numbers[index1]+numbers[index2]<target){
12
                index1++;
13
            }
14
        }
15
        ans[0] = index1+1;
16
        ans[1] = index2+1;
17
        return ans;
18
    }
19
}

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$。

方法二：二分搜索

在数组中找到两个数，使得它们的和等于目标值，可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。

1
class Solution {
2
    public int[] twoSum(int[] numbers, int target) {
3
        for (int i = 0; i < numbers.length; ++i) {
4
            int low = i + 1, high = numbers.length - 1;
5
            while (low <= high) {
6
                int mid = (high - low) / 2 + low;
7
                if (numbers[mid] == target - numbers[i]) {
8
                    return new int[]{i + 1, mid + 1};
9
                } else if (numbers[mid] > target - numbers[i]) {
10
                    high = mid - 1;
11
                } else {
12
                    low = mid + 1;
13
                }
14
            }
15
        }
16
        return new int[]{-1, -1};
17
    }
18
}

复杂度分析：

  • 时间复杂度：$O(nlogn)$。
  • 空间复杂度：$O(1)$。