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

想法

1. 我們可以用兩個指針分別指向第一個元素(指針low)跟最後一個數字(指針high)
2. 比較兩個數字：
3. 當兩個數字的和相等於目標數時，我們就找到了題目的唯一解
4. 如果數字和小於目標，把指著第一個數字的指針 low 往後走，使數字和變大
5. 如果數字和大於目標，把指著最後一個數字的指針 high 往前走，使數字和變小
6. 一直重複到找到解為止

用範例實際走一遍

假設 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