兩數之和

redeye

題目：

給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出和為目標值 target 的兩個整數，並返回它們的數組下標。

你可以假設每種輸入只會對應一個答案，並且你不能使用兩次相同的元素。

你可以按任意順序返回答案。

範例 1：

輸入： nums = [2, 7, 11, 15], target = 9
輸出： [0, 1]
解釋：因為 nums[0] + nums[1] == 9，所以返回 [0, 1]。

範例 2：

輸入： nums = [3, 2, 4], target = 6
輸出： [1, 2]
解釋：因為 nums[1] + nums[2] == 6，所以返回 [1, 2]。

範例 3：

輸入： nums = [3, 3], target = 6
輸出： [0, 1]
解釋：因為 nums[0] + nums[1] == 6，所以返回 [0, 1]。

提示：

•	2 <= nums.length <= 10^4
•	-10^9 <= nums[i] <= 10^9
•	-10^9 <= target <= 10^9
•	只會存在一個有效答案

進階：

你能否設計出一個時間複雜度小於 O(n^2) 的算法？

這題要求在數組中找出兩個數字，它們的和為 target，並且返回它們的索引。進階部分要求將解法的時間複雜度降低，避免使用暴力法（O(n^2) 的解法）。

可以使用哈希表（字典）來優化時間複雜度，將解法的時間複雜度降低到 O(n)。

解答：


class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 使用字典來存儲數字和索引的對應關係
        num_map = {}
        
        for i, num in enumerate(nums):
            complement = target - num
            # 檢查 complement 是否已經出現在 num_map 中
            if complement in num_map:
                return [num_map[complement], i]
            # 如果沒有找到 complement，將當前數字和索引存入字典
            num_map[num] = i
        
        # 若無解，返回空列表（一般情況下不會到這一步）
        return []

解釋：

1.	num_map 是用來儲存每個數字的值和它對應的索引。
2.	在遍歷 nums 的每個數字時，計算 complement = target - num，這就是當前數字所需的另一個數字。
3.	如果 complement 已經存在於 num_map 中，則表示找到了兩個數字，它們的和是 target，所以返回它們的索引 [num_map[complement], i]。
4.	如果沒有找到，則將當前數字和索引存入 num_map 中，繼續查找。

輸入與輸出的範例：

# 範例 1
solution = Solution()
print(solution.twoSum([2, 7, 11, 15], 9))  # 輸出: [0, 1]，因為 2 + 7 = 9

# 範例 2
print(solution.twoSum([3, 2, 4], 6))  # 輸出: [1, 2]，因為 2 + 4 = 6

這樣的解法不僅簡潔，而且效率更高，時間複雜度是 O(n)，空間複雜度也是 O(n)。