LeetCode 1. two-sum - IHCT Blog - 遨遊星辰Among The Stars

題目連結：https://leetcode.com/problems/two-sum/description/

算是Leetcode最經典的題目之一了，所有初學者第一題應該都是從這裡開始的(包括我)，廢話不多說，開始！

Brute Force 暴力迴圈解

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n= len(nums)
        for i in range(n-1):
            for k in range(i+1, n):
                if (nums[i] + nums[k]) == target:
                    return [i, k]
        return [] # no solution

我一開始也是很輕鬆地寫出了一個迴圈解，不過這個寫法的缺點也很明顯，因為有兩個迴圈，我們的 時間複雜度會是O(n^2) ，不過只會使用到用於輸出的常數，所以 空間複雜度會是O(1) 。

Hash Table 雜湊表

使用雜湊表，就只需要把元素放到雜湊表一次，再透過其中一個答案反推，所以時間複雜度會是 O(n) ，但因為要創建雜湊表，所以空間複雜度也會是 O(n) 。

Two-pass Hash Table 遍歷兩次

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n= len(nums)
        num_map = {}

        #hash table
        for i in range(n):
            num_map[nums[i]] = i # 因為要找的是index，所以index放在value的位置

        for i in range(n):
            complement = target - nums[i]
            if complement in num_map and num_map[complement] != i:
                return [i, num_map[complement]]

        return [] # no solution 

可以簡單理解為a + b = target，所以targer - a = b
當目標與現在數字的差值如果在表中(也就是target - a = b在表中)、並且b的位置不等於a的位置(避免同一個元素被使用)。

One-pass Hash Table 遍歷一次

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n= len(nums)
        num_map = {}

        for i in range(n):
            complement = target - nums[i]
            if complement in num_map:
                return [num_map[complement], i] # return的順序會反過來
            num_map[nums[i]] = i # 這時候才把數字加到雜湊表

        return [] # no solution 

這個邏輯是先判斷再把數字加入雜湊表，所以第一個答案先被算出來也不會使判斷式成立，而是從後面的數字反推前面的，所以算出答案時的complement會是前面的答案，所以return的順序會反過來。