LeetCode两数之和实现时filter仅返回数组首个元素问题咨询

问题根因 #

• 你对filter方法的功能存在误解：Array.prototype.filter 仅做元素筛选，回调返回值会被转为布尔值，仅决定当前遍历的元素是否保留到结果数组中，不会将返回的索引替换原元素。
• 第一个符合条件的索引是0，而0在布尔判断中属于假值，导致对应的元素直接被过滤，第二个符合条件的索引是1属于真值，对应的mapped数组元素是2，所以最终你得到的结果是[2]。
• 现有逻辑还存在额外隐患：遇到重复值的测试用例（比如[3,3]）时，indexOf只会返回第一个元素的索引，会得到重复的索引，不符合题目「同一元素不能重复使用」的要求。

修复方案 #

改用哈希表存储已遍历元素和对应索引的映射，遍历数组时直接判断当前元素的差值（target - 当前元素值）是否存在于哈希表中，存在即可直接返回两个索引，不存在就将当前元素和索引存入哈希表，时间复杂度为O(n)，也能完美规避重复值的问题。

修复后完整代码如下：

const testArrs = {
    'first': [2,7,11,15],
    'second': [3,2,4],
    'third': [3,3]
}

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

// 测试用例验证
console.log(twoSum(testArrs['first'], 9)) // 输出 [0, 1]
console.log(twoSum(testArrs['second'], 6)) // 输出 [1, 2]
console.log(twoSum(testArrs['third'], 6)) // 输出 [0, 1]

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