Last Updated on 2022-01-09 by Clay
題目
Given a 1-indexed 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. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. The tests are generated such that there is exactly one solution. You may not use the same element twice.
Example 1:
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. We return [1, 2].
Example 2:
Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:
Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
Constraints:
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbersis sorted in non-decreasing order.-1000 <= target <= 1000- The tests are generated such that there is exactly one solution.
題目給定一組排序過後的一維陣列，跟所有 Two Sum 的題目一樣，我們需要找到陣列中的兩個元素，加總正好為 target，並回傳兩元素的 index。
順帶一提，這陣列的 index 限定從 1 開始計算起。
解題思路
這題不愧是 Easy… 我解題完後看了討論區，發現幾乎所有人都是共同的解法。要說這題的陷阱在哪，或許是在於如果你使用經典的一輪掃過去並確認是否等於之前儲存的差距值會 Timeout 吧。
我的解法是先設定好左右兩端點的 index 值，比較加總是否等於 target，如果等於就回傳正解，如果小於 target 就將右端點往左挪一個 index（將加總值減少）、反之則挪動左端點……（將加總值增加）
以下就直接看程式碼吧。
C++ 範例程式碼
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int l=0;
int r=numbers.size()-1;
while (l < r) {
if (numbers[l] + numbers[r] == target) break;
else if (numbers[l] + numbers[r] > target) --r;
else ++l;
}
return {l+1, r+1};
}
};Python 範例程式碼
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l = 0
r = len(numbers) - 1
while l < r:
if numbers[l] + numbers[r] == target: break
elif numbers[l] + numbers[r] < target: l += 1
else: r -= 1
return [l+1, r+1]