JavaScript 2 Sum（两数之和）最优解法代码原理咨询

以下是你提到的原代码：

function twoNumberSum(array, target) {
    const nums = {};
    for (const num of array) {
        const potentialMatch = target - num;
        console.log('potential', potentialMatch);
        if (potentialMatch in nums) {
            return [potentialMatch, num]
        } else {
            nums[num] = true;
        }
    }
}

核心逻辑 #

这个解法是典型的空间换时间优化，相比暴力两层循环的O(n²)时间复杂度，它的时间复杂度只有O(n)，是两数之和问题的最优解法之一。
核心思路非常直接：我们要找两个数相加等于target，那遍历到任意一个数num时，和它配对的数必然是target - num，我们只需要判断这个配对数之前有没有出现过即可。

逐行拆解 #

• const nums = {}：创建一个空JS对象作为哈希表，用来存储已经遍历过的数字，仅用数字作为对象的key，value存true只做存在标记使用。
• for (const num of array)：遍历输入数组的每一个元素，当前遍历到的元素记为num。
• const potentialMatch = target - num：计算当前数字需要的配对值，也就是如果存在另一个数和num相加等于target，那这个数一定等于target - num。
• if (potentialMatch in nums)：检查哈希表中是否已经存过这个配对值
  • 存在：说明我们之前已经遍历过这个配对数，直接返回[potentialMatch, num]即可得到正确结果
  • 不存在：把当前遍历到的num存入哈希表，供后续遍历到的元素做配对检查使用

示例演示 #

举个实际运行的例子更直观：
输入array = [3,5,-4,8,11,1,-1,6]，target = 10

1. 遍历到3：配对值是10-3=7，哈希表为空无匹配，存3到哈希表
2. 遍历到5：配对值是10-5=5，哈希表无匹配，存5到哈希表
3. 遍历到-4：配对值是14，无匹配，存-4
4. 遍历到8：配对值是2，无匹配，存8
5. 遍历到11：配对值是-1，无匹配，存11
6. 遍历到1：配对值是9，无匹配，存1
7. 遍历到-1：配对值是11，哈希表里已经存在11，直接返回[11, -1]，结果正确

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