跳至主要內容

Mr.He小于 1 分钟

解决方案

indexOf 的起始位置改为 i + 1,强制让它去查找当前元素之后的元素。这样既避免了找到自己,也符合“不能使用两次相同元素”的要求。 修改后的代码:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++){
        const left = nums[i]
        const right = target - left
        // 修改点:从 i + 1 开始查找
        const index = nums.indexOf(right, i + 1) 
        if(index > -1){
            return [i, index]
        }
    }
};

进阶建议

虽然修改后的代码可以通过测试,但使用 indexOf 在循环内部其实是一个 $O(N)$ 的操作,放在循环里会导致整体时间复杂度变为 $O(N^2)$。 更优的解法是使用 哈希表,可以将时间复杂度降低到 $O(N)$:

var twoSum = function(nums, target) {
    const map = new Map(); // 存储值和对应的下标
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        // 如果哈希表里有需要的补数,直接返回结果
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        
        // 否则将当前数字存入哈希表
        map.set(nums[i], i);
    }
};

这种解法只需遍历一次数组,效率更高。