167. Two Sum II - Input array is sorted

Difficulty: Medium, Frequency: N/A

link: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Binary search

$O(nlogn)$ runtime,

$O(1)$ space

相較上一題 Two Sum，這題改為 sorted array，第二層 for 迴圈的優化可以用 binary search，這邊先偷用 java 內建的 binary search。

java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int j = Arrays.binarySearch(numbers, target-numbers[i]);
            if (j > 0 && i != j) return new int[] {Math.min(i+1, j+1), Math.max(i+1, j+1)};
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Accepted
Runtime: 0 ms, faster than 100.00% of Java online submissions for Two Sum II - Input array is sorted.
Memory Usage: 39.2 MB, less than 65.63% of Java online submissions for Two Sum II - Input array is sorted.

改用自己寫的 binary search，好處是能自己設定起始點和終點，結果反而比較慢…

java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int j = binarySearch(numbers, target-numbers[i], i+1, numbers.length-1);
            if (j != -1) return new int[] {i+1, j+1};
        }
        throw new IllegalArgumentException("No two sum solution");
    }
    
    private int binarySearch(int[] array, int value, int start, int end) {
        while (start <= end) {
            int mid = (start + end) / 2;
            if (value > array[mid]) {
                start = mid + 1;
            }
            else if (value < array[mid]) {
                end = mid - 1;
            }
            else {
                return mid;
            }
        }
        return -1;
    }
}

Accepted
Runtime: 2 ms, faster than 22.41% of Java online submissions for Two Sum II - Input array is sorted.
Memory Usage: 39.4 MB, less than 38.37% of Java online submissions for Two Sum II - Input array is sorted.

Two pointers

$O(n)$ runtime,

$O(1)$ space

這個做法的概念很簡單，目標是要找矩陣內的某兩個元素總和，使用兩個index先指向最大值和最小值的元素，並開始往中間找。

如果兩元素總和比目標大，那就讓比較大的index往前移，如果兩元素總和比目標小，就讓比較小的index往後移，直到最後找到正解為止。

我一開始其實有想到這個做法，後來放棄了。當初覺得不太對的考量點，這樣只掃過一次的作法，會不會不小心錯過正確答案，需要倒退走呢？

仔細想想，其實並不會。舉例來說，有一個矩陣[a, b, c, d, e, f, g]，假設我們要找的組合是 c 和 e，檢查到 b 和 f 時只有兩種情況：

1. 如果 b + f > c + e，我們會嘗試 b 和 e 的組合，因為 b + e < c + e 所以下一個我們從 b 移到 c，就是正確答案。
2. 如果 b + f < c + e，我們會嘗試 c 和 f 的組合，因為 c + f > c + e 所以下一個我們會從 f 移到 e，就是正確答案。

所以如果答案存在，從兩邊往中間走一定有辦法遇到。

java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int i = 0, j = numbers.length - 1;
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum < target) {
                i++;
            } else if (sum > target) {
                j--;
            } else {
                return new int[] { i + 1, j + 1 };
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

Accepted
Runtime: 0 ms, faster than 100.00% of Java online submissions for Two Sum II - Input array is sorted.
Memory Usage: 38.9 MB, less than 88.82% of Java online submissions for Two Sum II - Input array is sorted.

python

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        i, j = 0, len(numbers)-1
        
        while i < j:
            two_sum = numbers[i] + numbers[j]
            if two_sum < target:
                i += 1
            elif two_sum > target:
                j -= 1
            else:
                return [i+1, j+1]

Accepted
Runtime: 64 ms, faster than 56.89% of Python3 online submissions for Two Sum II - Input array is sorted.
Memory Usage: 14.7 MB, less than 18.56% of Python3 online submissions for Two Sum II - Input array is sorted.

tags: leetcode