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

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};
    }
};
下面的按鈕可以直接分享🐹

歡迎留言分享你/妳的看法唷,信箱不會公開😀