【LeetCode-紀錄&教學】167. Two Sum II – Input array is sorted

原文題目

Given an array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2,
where 1 <= answer[0] < answer[1] <= numbers.length.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

中文解釋

給一個已排序的陣列以及一個整數Target，
我們要返回兩個數，相加剛好是Target的值。

範例

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

技巧

1. 雙指針逼近
2. 刪去法

解題想法

看到這個題目第一個想到的是暴力解，
很簡單啊，我只要巢狀兩個for loop不就行了，
但遺憾的是，這個時間複雜度O(n²)不是我們想要的，
Commit結果絕對是Failed，然而我們可以用雙指針的方式求解，
因為是已排序的遞增陣列，右邊一定比左邊的值來的大，
以刪去的方式思考，刪去不可能的數值，
在陣列的左右兩側各放一個指針，
當 l 及 r 指到的位置相加小於target，則 l 指針向右1格，
反之，則 r 指針向左1格，直到等於target的數值
這樣就可以把時間複雜度降到O(n)

Code

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int l=0, r=nums.size()-1, sum;
        while(l<r){
            if (nums[l] + nums[r] < target)
                l++;
            else if (nums[l] + nums[r] > target)
                r--;
            else
                break;
        }
        return vector<int>{l, r};
    }
};