LeetCode两数之和解法思路溯源：为何采用target - num？

我当初第一次琢磨两数之和问题的时候，也先从最基础的思路开始捋，慢慢才摸到哈希表解法的门道，咱们一步步拆解：

1. 先拆解问题本质，自然得到核心步骤 #

问题要求找两个数 a 和 b，满足 a + b = target。那换个角度想：如果我现在拿到了一个数 num（也就是其中一个数，比如a），那另一个需要的数 b 不就是 target - num 吗？这就是你疑惑的 n = target - num 的来源——把加法问题转换成了**“找已遍历过的数里有没有等于target减当前数”**的查找问题，完全是从问题本身的等式变形来的，非常自然。

2. 从暴力解法到优化思路 #

最开始谁都会想到暴力解法：遍历每个数，然后再遍历剩下的所有数，看有没有等于 target - num 的。但这样做每次查找都要扫一遍数组，时间复杂度是 O(n²)，数据量大的时候肯定慢。

这时候就会想：能不能把查找的速度提上来？ 我们需要一种能快速判断某个数是否存在、还能直接拿到它索引的数据结构——哈希表（Python里的字典）正好符合这个需求，它的查找时间是 O(1)。

3. 梳理哈希表解法的完整逻辑 #

基于上面的思路，就能一步步构思出代码的流程：

• 初始化一个空字典，用来存已经遍历过的数和它对应的索引（键是数值，值是索引，因为我们最终要返回索引）。
• 遍历数组，用 enumerate 同时拿到当前数的索引和数值：
  • 计算我们需要找的配对数 n = target - num。
  • 检查 n 是否在字典里：
    • 如果不在，说明之前没遇到过能和当前数配对的数，就把当前的数值和索引存进字典里，继续遍历下一个数。
    • 如果在，说明之前已经遇到过这个配对数了，直接返回那个数的索引和当前索引就行。

结合示例走一遍流程 #

拿你给的示例 nums = [2,7,11,15], target = 9 来说：

1. 遍历第一个数2，索引0：n = 9-2=7，字典是空的，没有7，所以存 {2: 0}。
2. 遍历第二个数7，索引1：n =9-7=2，字典里有2对应的索引0，直接返回 [0,1]。

完整代码（带注释） #

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 初始化哈希表，存储已遍历数值与对应索引
        num_index_map = {}
        # 同时遍历数组的索引和数值
        for idx, num in enumerate(nums):
            # 计算当前数需要的配对数
            complement = target - num
            # 检查配对数是否已存在于哈希表中
            if complement in num_index_map:
                # 存在则返回两个数的索引
                return [num_index_map[complement], idx]
            # 不存在则将当前数和索引存入哈希表
            num_index_map[num] = idx

内容的提问来源于stack exchange，提问作者confused_anteater