小于 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);
}
};
这种解法只需遍历一次数组,效率更高。