2025/07/28

这个问题看起来很简单，但最简单的解法并不是最优的。最暴力的解法就是循环遍历数组中所有的元素对。我第一次提交那个垃圾暴力解法后，有了一个“补数”的想法，但补数其实无非是把 if 条件 “a + b = target” 改写成 “a = target - b”，本质上还是暴力解法。暴力解法的时间复杂度是 $O (n^{2})$ 。我当时想不到第二种解法。

第二种解法涉及到哈希算法。我去复习了哈希算法（见我的文章），但发现跟这个问题看起来好像没关系。实际解法是：把数组转换成一个字典，用来存储值到索引的映射（需要 $O (n)$ 时间），然后在字典中循环查找目标配对。不同点在于，对于字典中的每个元素，我们计算它的补数，然后可以立即知道补数是否存在于字典中（ $O (1)$ ），而无需内层循环。

一开始看起来像是在作弊，但最终我意识到 Python 的字典其实就是哈希表，这就是哈希算法的实现。这个解法只是利用哈希表加速查找操作。时间复杂度是 $O (n)$ ，比暴力解法好很多。

2025/10/16

思路：用字典反存下标（哈希），按值搜索 $O (1)$

手写代码：

def twoSum(nums, target):

    hash_dict = {}
    for i, num in enumerate(nums):
        hash_dict[num] = i
    
    for i, num in enumerate(nums):
        if target - num in hash_dict:
            return [i, hash_dict[target - num]]

评价：思路正确，不过这里有个问题，字典的键不能重复。

推荐思路：可以边查边存，不会出现遗漏的，因为它是配对，用前面的查后面找不到，但过后一定有后面查前面，一定能找到，所以不会漏。这样也能解决存到字典里重复的问题，因为是先查再存。