如何优化LeetCode两数之和题解，降低遍历校验元素的耗时

你当前使用的暴力两两比对思路时间复杂度为O(n²)，每一个元素都要和剩余所有元素做求和校验，同时代码中调用的indexOf、lastIndexOf方法本身也有*O(n)*的时间开销，数组长度达到百万级时必然触发超时。另外原代码依赖indexOf和lastIndexOf查找下标，当数组存在重复元素时还会出现下标匹配错误的问题。

优化思路采用空间换时间的策略，利用哈希表（JavaScript中可直接用Map）存储已遍历元素的值和对应下标，仅需一次遍历即可完成校验：对当前遍历的元素num，计算需要的互补值target - num，直接查询哈希表中是否存在该互补值，存在则直接返回两个下标，不存在就将当前元素和下标存入哈希表继续遍历。

优化后的代码如下：

var twoSum = function(nums, target) {
    // 哈希表存储 元素值: 对应下标
    const numMap = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        // 查到互补值直接返回结果
        if (numMap.has(complement)) {
            return [numMap.get(complement), i];
        }
        // 没查到就把当前元素和下标存入哈希表
        numMap.set(nums[i], i);
    }
    // 无匹配返回空数组（符合LeetCode题目输出要求）
    return [];
};

// 测试用例
console.log(twoSum([5, 2, 5, 5, 1, 3, 6, 8, 4, 3, 2, 7], 14));

优化后的效果：

• 时间复杂度降到O(n)，仅需遍历数组一次，百万级输入也可正常运行
• 空间复杂度为O(n)，最差情况下存储整个数组的元素，属于算法题中可接受的开销
• 规避了原代码中重复遍历、下标查找冗余、重复元素匹配错误的问题，逻辑简洁清晰，符合LeetCode题目的输出规范

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