3-167.两数之和

题目描述：

解题思路：

1、双指针法

设置两个指针i和j，每次比较移动i或者j。

当时只想到这种解法，并没有考虑到这种解法是否会过滤掉正确答案。事实上是不会过滤掉正确答案的，原因如下：

? 假设numbers[i] + numbers[j] == target

? 有0<= i < j <= numbers.length-1

? 在移动i,j的过程中，必然有一方先到达指定的i或者j。

? 假设i先到达，则有numbers[i] + numbers[j] > target,此时只有可能是j左移，直到正确位置

? 如果j先到达，则有numbers[i] + numbers[j] < target，此时只有可能是i右移。因此答案唯一。

2、二分查找法

可以首先固定第一个数，然后寻找第二个数。第二个数等于target-第一个数。然后在寻找第二个数的时候，使用二分查找。

为了避免重复，在寻找第二个数的时候，只在第一个数的右侧寻找。

代码：

//1、双指针法
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0;
        int j = numbers.length-1;
        int[] ans = new int[2];
        while(i < j){
            if (numbers[i] + numbers[j] == target){
                ans[0] = i + 1;
                ans[1] = j + 1;
            }
            if (numbers[i] + numbers[j] > target){
                j = j - 1;
            }else{
                i = i + 1;
            }
        }
        return ans;
    }
}

//2、二分查找法
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] ans = new int[2];
        for(int i = 0;i < numbers.length;i++){
            int low = i + 1;
            int high = numbers.length - 1;
            while(low <= high){
                int mid = (low + high) / 2;
                if (target - numbers[i] == numbers[mid]){
                    ans[0] = i + 1;
                    ans[1] = mid + 1;
                }
                if (target - numbers[i] < numbers[mid]){
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }
        }
        return ans;
    }
}

3-167.两数之和

原文：https://www.cnblogs.com/forrestyu/p/14646022.html