LeetCode 刷題紀錄 |167. Two Sum II — Input array is sorted (Easy)
這題是 Two Sum 的變形題,他假設輸入的數列會是已經排列好的
Two Sum II — Input array is sorted
Question
Link: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
Note:
- Your returned answers (both index1 and index2) are not zero-based.
- You may assume that each input would have exactly one solution and 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.
Example 2:
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Example 3:
Input: numbers = [-1,0], target = -1
Output: [1,2]
Constraints:
2 <= nums.length <= 3 * 104
-1000 <= nums[i] <= 1000
nums
is sorted in increasing order.-1000 <= target <= 1000
Answers
這題要學怎麼善用數列已由小到大排列的特性
Solution 1: Two Pointers
想法
- 我們可以用兩個指針分別指向第一個元素(指針low)跟最後一個數字(指針high)
- 比較兩個數字:
- 當兩個數字的和相等於目標數時,我們就找到了題目的唯一解
- 如果數字和小於目標,把指著第一個數字的指針 low 往後走,使數字和變大
- 如果數字和大於目標,把指著最後一個數字的指針 high 往前走,使數字和變小
- 一直重複到找到解為止
用範例實際走一遍
假設 input array: nums = [1, 2, 3, 4, 7], 目標 target = 6
起始 low = 0, high = nums.length — 1
當 low < high 時,sum = nums[low] + nums[high]
low = 0 < high = 4, sum = 1 + 7 = 8 , 8 > 6,所以把high的指針往前移動, high -=1
low = 0 < high = 3, sum = 1 + 4 = 5, 5 < 6,所以把low往後移動, low += 1
low = 1 < high = 3, sum = 2 + 4 =6, 6 = 6, 找到唯一解, 此時 return [low+1, high + 1] 因為要回傳第幾個數字
ans = [2, 4]
Javascript 程式碼如下
var twoSum = function(nums, target) {
let low = 0;
let high = nums.length - 1;
while (low < high) {
let sum = nums[low] + nums[high];
if (sum === target) {
return [low + 1, high + 1];
} else if (sum < target) {
low++;
} else {
high--;
}
}
return [-1, -1];
};
複雜度
- Time complexity: O(n), n個元素最多只會被造訪1次
- Space complexity: O(1), 只用到兩個指針
Python 程式碼
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
start = 0
end = len(numbers) - 1
res = []
while start < end:
sum = numbers[start] + numbers[end]
if target > sum:
start+=1
elif target < sum:
end-=1
else:
return [start + 1, end + 1]
Reference:
新手上路,如果有寫錯的地方歡迎大力糾正,歡迎留言討論或是到我的Socials找我~謝謝觀看!
About Roy
Social Media
Facebook — RoyWannago
Twitter — @roywannago
Instagram — @royflwdesign
Website — roywannago.com