Leetcode 167，三种解法，最佳时间复杂度为O(n)

给定一个数，求有序数组中两个数的和刚好等于它，返回索引

最简单直接的就是两层循环，时间复杂度为O(n^2)

    public int[] twoSum(int[] numbers, int target) {
        for(int i = 0; i < numbers.length; i ++){
            for(int j = i + 1; j < numbers.length; j ++){
                if(numbers[i] + numbers[j] == target){
                    int[] index = {i+1, j+1};//index[0] = i + 1;
                    return index;
                }
            }
        }
        throw new IllegalArgumentException("the input has no solution !");
    }

第二种方法

是根据有序数组的性质，在第二层开始使用二分法进行查找
时间复杂度为O(nlog^n)

    public static int[] twoSum(int[] numbers, int target) {

        for(int i = 0; i < numbers.length; i ++){
            int l = i + 1;
            int r = numbers.length;
            while(l < r){
                int mid = l + (r - l) / 2;
                if(target - numbers[i] > numbers[mid])
                    l = mid + 1;
                else if(target - numbers[i] < numbers[mid])
                    r = mid;
                else { //target - numbers[i] == numbers[mid]
                    int[] index = {i+1, j+1};//index[0] = i + 1;
                    return index;
                }
            }
        }
     throw new IllegalArgumentException("the input has no solution !");
    }

第三种

时间复杂度为O(n)，对撞指针法，设置两个指针，一左一右，如果两者相加大于target，说明数字太大了，右边的向左移，如果小于target，说明太小了，左边的往右移。

public static int[] twoSum(int[] numbers, int target) {
        
        int l = 0;
        int r = numbers.length - 1;
        while (l < r){
            if(numbers[l] + numbers[r] == target) {
                int[] index = {l + 1, r + 1};
                return index;
            }
            if(numbers[l] + numbers[r] < target)
                l++;
            if(numbers[l] + numbers[r] > target)
                r--;
        }

        throw new IllegalArgumentException("input error !");
    }