1 題目描述

這是一道經典的 Two Sum 問題，要求從一個整數數組 nums 中找出兩個數字，使它們的和等於給定的目標值 target，並返回這兩個數字的索引。每個輸入保證有且只有一個解，且同一元素不能被重複使用。答案的返回順序可以是任意的。

2 解法

2.1 暴力解

簡單粗暴些，兩重循環，遍歷所有情況看相加是否等於目標和，如果符合直接輸出。

時間複雜度：O(n²)
空間複雜度：O(1)

public int[] twoSum(int[] nums, int target) {
    int []ans=new int[2];
    for(int i=0;i<nums.length;i++){
        for(int j=(i+1);j<nums.length;j++){
            if(nums[i]+nums[j]==target){
                ans[0]=i;
                ans[1]=j;
                return ans;
            }
        }
    }
    return ans;
}

2.2 我的想法

手動建立HashTable
因為Two Sum的核心在於使用Hash，因此這邊我使用Hash Table來解這題。關於Hash Table的詳解可以參考這篇文章。使用Hash Table 的核心概念是，如果今天你要找 complementary = target - v 的值，你可以先把所有的值放進 Hash Table，把要找的值當作 key，該值在nums中的index當作HashTable中的value，然後直接在 HashTable(key) 就可以直接回傳對應的 index。這樣的時間複雜度只有 O(1)。

時間複雜度：O(n)
空間複雜度：O(n)



class MyHashTable:
    def __init__(self, num_list):
        self.len = len(num_list) * 2
        self.buckets = [None for i in range(self.len)]
        self.init_buckets(num_list)

    def init_buckets(self, num_list):
        if num_list is None:
            return
        for i, v in enumerate(num_list):
            self.__setitem__(i, v)

    def __getitem__(self, value):
        hash_value = abs(hash(value))
        index = hash_value % self.len
        while self.buckets[index] is not None:
            if self.buckets[index][1] == value:
                return self.buckets[index][0]
            index = (index + 1) % self.len
        return None

    def __setitem__(self, key, value):
        hash_value = abs(hash(value))
        index = hash_value % self.len
        while self.buckets[index] is not None:
            index = (index + 1) % self.len
        self.buckets[index] = (key, value)


class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hash_list = MyHashTable(nums)
        for i, v in enumerate(nums):
            find = target - v
            tar_index = hash_list.__getitem__(find)
            if tar_index != i: # 確保不是相同的index否則會同一個值拿兩次 [3, 3] 找 ６ 回傳 [0,0]
                if tar_index is not None:
                    return [i, tar_index]
        return None

MyHashTable.__init__ 和 MyHashTable.init_buckets 的時間複雜度都是 O(n)。
MyHashTable.__getitem__ 和 MyHashTable.__setitem__ 的平均時間複雜度是 O(1)，最壞情況下是 O(n)。
Solution.twoSum 的時間複雜度是 O(n)

因此，整個程式的時間複雜度是 O(n) 滿足題目要求，不使用 O(n²) 的暴力解法。

2.3 最佳解

但是在 python 根本不需要自己建立 HashTable ，因為 python 內建的 dict 或是 set 就是 HashTable 的實現，因此可以直接使用內建的 HashTable 來解這題。

時間複雜度：O(n)
空間複雜度：O(n)

class Solution(object):

    def twoSum(self, nums, target):
        numSet = {}
        # build hash table （解法1是自己建立的HashTable，這裡採用Python內部的）
        for i, v in enumerate(nums):
            numSet[v] = i

        # find the complement
        for i, v in enumerate(nums):
            complement = target - v
            if complement in numSet and numSet[complement] != i:
                return [i, numSet[complement]]

        return [] # No solution Found


if __name__ == '__main__':
    nums = [3, 3]
    target = 6
    print(Solution().twoSum2(nums, target))