LeetCode两数之和(Two Sum) JS代码返回错误索引问题排查

错误原因 #

• 内层循环逻辑错误：内层变量a固定从1开始遍历，没有设置a > i的约束，会出现两种不符合要求的情况：1）同一个索引被重复使用，比如示例中i=1,a=1时，nums[1] + nums[1] = 3+3=6刚好命中target，导致错误的索引1被加入结果；2）同一对索引会被正反匹配两次，比如i=2,a=3和i=3,a=2都会命中4+2=6，导致冗余结果。
• 结果处理逻辑错误：题目要求返回两个不重复的索引，你先把所有命中的索引全部存入数组再整体去重的逻辑完全不符合需求，还会把错误命中的索引混入结果。如果开启你注释掉的slice(0,2)逻辑，就会取到错误的前两个索引[1,2]，和你遇到的输出结果一致。
• 缺少提前终止逻辑：找到符合要求的索引对后没有立刻返回，后续遍历的冗余结果会干扰最终输出。

修复方案 #

暴力解法修复（保持双循环逻辑的前提下） #

修改内层循环起始值为i+1，匹配到符合要求的索引对后直接返回，无需额外的去重、切片操作，修复后代码如下：

var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++) {
        // 内层从i+1开始，保证两个索引不重复、不重复匹配同一对
        for(let a = i + 1; a < nums.length; a++) {
            if(nums[i] + nums[a] === target) {
                return [i, a];
            }
        }
    } 
    return [];
};
console.log(twoSum([1,3,4,2],6)) // 输出 [2,3] 符合预期

优化方案（哈希表，时间复杂度O(n)） #

如果需要更高的执行效率，可以用哈希表存储已经遍历过的元素和对应的索引，单次遍历即可得到结果：

var twoSum = function(nums, target) {
    const map = new Map();
    for(let i = 0; i < nums.length; i++) {
        const diff = target - nums[i];
        if(map.has(diff)) {
            return [map.get(diff), i];
        }
        map.set(nums[i], i);
    }
    return [];
};

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