1 題目描述

從numbers裡面找出兩個數字，使得他們的和等於target，並且返回這兩個數字的索引，且索引是從1開始。

2 解法

2.1 暴力解法

最純的暴力破解法，就是O(N^2)遍歷所有的組合，找出符合條件的組合。

1
2
3
4
5
6
7

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        for i in range(n):
            for j in range(i+1, n):
                if numbers[i] + numbers[j] == target:
                    return [i+1, j+1]

2.2 Speed O(N)

這題的關鍵是，我們該如何避免檢查那些不可能的組合？

我一開始沒有立刻領悟出 numbers[right] + numbers[left] 與 target 之間的關係，因為numbers是排序過的，所以我們可以利用這個特性，來找出答案。
舉例來說：

• left pointer 指向最小的數字
• right pointer 指向最大的數字
• 如果numbers[right] + numbers[left] 導致超過 target 這意味著什麼？
  • 這意味著我們需要更小的數字，因此我們將right pointer往左移動，讓數字變小。
• 如果numbers[right] + numbers[left] 導致遠低於 target 這意味著什麼？
  • 這意味著我們需要更大的數字，因此我們將left pointer往右移動，讓數字變大。
• 你會發現，兩個pointer往中間移動，每個pointer都會遍歷一次，這樣的時間複雜度是O(N)。

1
2
3
4
5
6
7
8
9
10
11

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

3 結語

這題的精華在於，你能不能發現有序的numbers，可以幫助你避免檢查不必要的組合。然後我最大的困難在於，我要怎麼確保window移動的時候，縮圈的方式不會錯過最佳解？以這個例子來說，既然要縮windows，我們是真的當前的window之外的組合都不可能是答案，才要縮圈。這也是為什麼這題的numbers必須排序過，才可以使用這個技巧。

為什麼，tot太大時，我們除了將right pointer往左移動使其變小，為什麼不需要重新將left pointer往左移動來檢查呢？

• 這是因為，我們今天right在當前的位置，是因為我們已經檢查過right+1的所有組合，然後left移動到與right相加時超過target的位置
• 因為移動過後的left與right+1相加的結果是太大，所以我們將right往左移動，讓數字變小，得到目前的right和left
• 現在我們因為right與left的組合太大，除了right pointer往左移動外，我們還去碰left pointer，這是多餘的。
• 因為 right + (left-1) 一定會小於 (right+1) + (left-1)，這是已經比較過的組合，也因為當時太小，才會把left pointer往右移動得到left
• 然後你現在又說移動left-1，就不合理，因為一定會因為太小，又把left pointer往右移動，這樣就是重複的動作。