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

LeetCode链接：167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

思路一：用双指针，指针left指向0的位置，指针right指向array.length - 1的位置，当left < right时，如果left + right < targe执行left++，如果left + right > targe执行right--,如果left + right = targe返回new int[left + 1, right + 1]

时间复杂度：O(n)

java代码：

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

        return new int[]{-1,-1};

    }



}

思路二：使用二分支查找，遍历数组，用target-array[i]得出另外一个目标元素，并用二分查找法找到目标元素的位置

时间复杂度：O(nlongn)

java代码：

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