LeetCode - 167. Two Sum II - Input array is sorted 两数之和 II - 输入有序数组

Question

题目

解析

两种做法：

• 对于每一个 arr[i] ，在后面的有序数组中二分查找有没有可以匹配的，时间复杂度 n * logn ；
• 使用双指针，因为是有序的，所以可以通过比较大小决定哪个指针的移动，时间复杂度 n ；

class Solution {
    //n * logn
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            // binary search
            int L = i + 1, R = numbers.length - 1;
            while (L <= R) {
                int mid = L + (R - L) / 2;
                if (numbers[mid] + numbers[i] == target)
                    return new int[]{i + 1, mid + 1};
                else if (numbers[mid] + numbers[i] < target)
                    L = mid + 1;
                else
                    R = mid - 1;
            }

        }
        return null;
    }
}

双指针:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int l = 0, r = numbers.length - 1; l < r; ) {
            if (numbers[l] + numbers[r] == target)
                return new int[]{l + 1, r + 1};
            else if (numbers[l] + numbers[r] < target)
                l++;
            else
                r--;
        }
        return null;
    }
}