【Leetcode 完整解答筆記】167. Two Sum II – Input array is sorted

提供一個陣列以及一個目標數字,輸出陣列中相加得到目標數字的索引。

題目URL點擊這裡

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.

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 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.

Python 解答 1:利用字典法

這裡分享 Python 的三個解法,皆來自 leetcode 上的大神,來源在這裡

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        dic = {}
        for i, num in enumerate(numbers):
            if target-num in dic:
                return [dic[target-num]+1, i+1]
            dic[num] = i

這裡使用了 enumerate 是為了同時使用 i 以及 numbers 中的個別元素 num。

以以下的輸入為例:

numbers = [2,7,11,15], target = 9

當 i=0,target-num = 9-2=7,7 不在dic裡面,於是進入 dic[num] = i,因此{0:’2′}。

當 i=1,target-num = 9-7=2,由於 2 已經在 dic 裡頭,return [dic[2]+1, 1+1],也就是return[1,2]。

為甚麼回傳 [dic[target-num]+1, i+1]?

為甚麼回傳 [dic[target-num]+1, i+1],而不是 [dic[target-num], i]?

題目告訴我們第一個 index 為 1,而不是我們常用的 0,而存入 dic 為 0,因此 dic[target-num] 需要 +1。

至於 i+1 同樣是因為題目要的 index 和我們常用的 index 多了 1,因此也需要 +1。

Python 解答 2:雙指標

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers)-1
        while l < r:
            s = numbers[l] + numbers[r]
            if s == target:
                return [l+1, r+1]
            elif s < target:
                l += 1
            else:
                r -= 1

這是 Python 中常見雙指標的方法。

有兩個指標,但兩個指標是獨立進行的。

我們來仔細看程式細節。

l, r = 0, len(numbers)-1

同樣假設最左邊為 0,最右邊為 r。

    s = numbers[l] + numbers[r]
    if s == target:
        return [l+1, r+1]
    elif s < target:
        l += 1
    else:
        r -= 1

同樣剛剛的例子為例。

numbers = [2,7,11,15], target = 9

第一輪,s=numbers[0]+numbers[3]=17
s>target ,r=2

第二輪,s=numbers[0]+numbers[2]=13
s>target ,r=1

第三輪,s=numbers[0]+numbers[1]=9
return[1,2]

這樣就完成啦。

這個解答中,l 和 r 分別都是指標,當 s>target 時,r 向前進一步;當 s<target 時,l 往後退一步。

Python 解答 3:二分法

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            l, r = i+1, len(numbers)-1
            tmp = target - numbers[i]
            while l <= r:
               mid = l + (r-l)//2
               if numbers[mid] == tmp:
                   return [i+1, mid+1]
               elif numbers[mid] < tmp:
                   l = mid+1
               else:
                   r = mid-1

這個二分法和之前提到的二分法如出一輒,只是在利用二分法前,先算出tmp,tmp = target – numbers[i] 。

如果在陣列中找不到 tmp,則在 for 迴圈中繼續尋找。

C 解答:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
    int *reval = (int*)malloc(sizeof(int)*2);
    *returnSize = 2;
    
    int left, right;
    left = 0; right = numbersSize-1;
    for(;;) {
        if(numbers[left] + numbers[right] > target)
            right--;
        else if(numbers[left] + numbers[right] < target)
            left++;
        else {
            reval[0] = left+1;
            reval[1] = right+1;
            return reval;
        }   
    } 
}

Leave a Comment

Your email address will not be published. Required fields are marked *