Leetcode刷題日記 - #1 Two Sum

題目請自行上Leetcode閱讀

1. 總和：題目是需要找出Array裡面的兩個數字，數字相加，結果必是target。假設target是6，你看到一個數字4，那麼，要找出可以相加為6的數字，一定是2。如果Array裏面有2這個數字，就找到解答了，如果沒有2這個數字，就表示數字4一定不是解答。
2. 尋找：從上面的敘述來看，這題的關鍵是如何我看到數字4，我要問我自己一個問題，2是不是在這個Array裏面，解法可以是直接loop這個Array一次去尋找，但是一個一個找效率比較差O(n)，有沒有更好的找法？
3. HashTable：想到要省去loop，第一個會想到的是可以快速以O(1)方式得到資訊的HashTable，到這裡，這題的解答已經呼之欲出了。
4. 解法：

Loop Array一次去計算每一個數字的「另外一半是誰」，例如Example = [2,3,4], Target = 6

那麼，HashTable裡面儲存的數字會是 {4: 0, 3: 1, 2: 2}

同時也看現在的數字nums[i]，在HashTable裡面是不是已經有另外一半了

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        temp: dict = {} # key = diff, value = index
        for i in range(len(nums)):
            diff = target - nums[i]
            if temp.get(nums[i]) is not None:
                return [temp[nums[i]], i]
            temp[diff] = i

結語：這題的關鍵在於前面提到的1和3，只要記住這兩點就好了。HashTable是一個經常拿來以空間換時間的資料結構，在各種考題裡都很好用。