解题思路

二分解法

1. 依次遍历每一个数据，numbers[i]。
2. 对于每一个numbers[i],都在后面的有序数组中寻找target-numbers[i].
3. 这里的寻找方法使用二分搜索法
4. 如果找到直接返回，否则继续遍历下一个数据
5. 时间复杂度O(nlogn)

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        for(int i=0;i<n;i++){
            int remain = target-numbers[i];
            //返回二分查找法后的结果
            int search = binarySearch(numbers, i+1, remain);
            //没有解则继续 有解则返回答案
            if(search==-1)
                continue;
            else
                return new int[]{i+1,search+1};
        }
        return null;
    }
    //二分查找法 输入的是二分查找法的下标
    public int binarySearch(int[] nums,int begin,int target){
        //在【l,r】左闭右闭的区间内进行二分查找法
        int l=begin;
        int r=nums.length-1;
        while(l<=r){
            int mid = (l+r)/2;
            if(nums[mid]==target){
                return mid;
            }
            if(nums[mid]<target){
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        return -1;
    }
}
// time O(n*log(n))

对撞指针

目标是要寻找两个索引，一左一右存在。

1. 初始化选择最左侧数字i,最右侧数字j
2. 判断nums[i]+nums[j]==target
3. 如果相等直接返回下标
4. 如果>target说明 需要使整体的值变小才可能相等
5. 又因为是有序数组，所以应该将j降低，j—
6. 如果<target说明 需要使整体的值变大才可能相等
7. 又因为是有序数组，所以应该将i增大,i++
8. 直到i==j跳出循环

public int[] twoSum(int[] numbers, int target) {
        if(numbers==null||numbers.length<2)
            return null;
        //l,r表示左右两个指针，最开始分别在两端
        int l = 0;
        int r = numbers.length-1;
        //循环结束的条件是l==r 指针撞在了一起
        while(l<r){
            //找到直接返回
            if(numbers[l]+numbers[r]==target)
                return new int[]{l+1,r+1};
            //和大于target 调小r
            if(numbers[l]+numbers[r]>target)
                r--;
            //和小于target 调大l
            else
                l++;
        }
        return null;
    }