167. Two Sum II - Input Array Is Sorted - Medium

前往題目

想法

• 2 pointers
• 每種組合都試，但兩數之合一旦超過target直接跳過當前left pointer

思路

1. 左右指針，一個指起點一個指終點
2. 當左右指針之和小於target，代表要讓和變大才有可能符合target，所以要移動左邊的pointer往右，移動右邊的會出界
3. 反之，移動右邊的往左，因為往右就算沒出界，和會變更大

題目保證了一定有解，所以往內縮到最後一定會找到解

Code

Discussion

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;

        while (numbers[l] + numbers[r] != target) {
            // Should be bigger
            if (numbers[l] + numbers[r] < target) {
                ++l;
            } else { // Should be smaller
                --r;
            }
        }

        return new int[]{l + 1, r + 1};
    }
}