題目背景

這個題目用常規的雙循環就可以完成。
但不是最優解。為什么？

看看他的步驟數：
N =[3，2，4]
求結果為6的兩個元素坐標如下，
1). 3+2 = 5 不等于
2). 3+4 = 7 不等于
3). 2+4 = 6 等于，獲取坐標[1，2]

求N的步驟數規律：
2個數 = 1 個步驟
3個數 = 3 個步驟
4個數 = 6 個步驟
5個數 = 10 個步驟
6個數 = 15 個步驟
7個數 = 21 個步驟
......

如果有N個元素, 則需要N個步驟，那么記作 O(N）。下面分析那么這個算法的大O是：

約等于 N(N) = $ N^2 $

這個算法的時間復雜度為：O($ N^2 $).
有什么辦法能降低這個時間復雜度嗎?

解題思路

def twoSum(nums, target):
    # 創建一個哈希表來存儲值和索引
    num_to_index = {}

    # 遍歷數組
    for i, num in enumerate(nums):
        # 計算當前數字的補數
        complement = target - num

        # 檢查補數是否在哈希表中
        if complement in num_to_index:
            # 如果在，返回補數的索引和當前索引
            return [num_to_index[complement], i]

        # 如果不在，將當前數字及其索引存入哈希表
        num_to_index[num] = i

    # 如果沒有找到符合條件的兩個數，返回空列表或拋出異常
    return []

print(twoSum([3, 2, 4], 6))

模擬運行過程：

# {} 創建map

# 1) 6 - 3 = 3 , 判斷 3不在map,繼續
# map加上{3:1}

# 2) 6 - 2 = 4 , 判斷 4不在map,繼續
# map加上{3:1,2:2}

# 3) 6 - 4 = 2 , 判斷 2在map ，返回當前4和2的坐標，結束。
# map{3:1,2:2}