我如何减少检查这个leetcode中的每个值所花费的时间?

Question

所以在LeetCode上，我需要返回等于目标数的两个数的和。这是一个leetcode "easy"类型。我以前从来没有做过leetcode，所以我决定试一试。马上，我就能解决这个问题了，但我的解决方案是不合理的，因为它将数组中的每个数字相互检查。因此，如果输入是一百万个数字，那么它将为每个数字检查一百万次。

值得注意的是，虽然我的程序可以工作，但由于时间限制，它可以提交。

我不确定优化这个的数学解决方案是什么。我现在要重新学习数学，学习我的弱项。

代码:

var twoSum = function(nums, target) {
let total = [];
let inc = 1;
let intVal = 0;

let startingPos = nums[intVal];
let nextPos = nums[inc];

for(let x = 0; x < nums.length; x++){
// Do not check the value of position 1 with position 2
if(nums.indexOf(startingPos) === nums.lastIndexOf(nextPos)){
nextPos++;
}

if(startingPos + nextPos === target){
console.log(`First Value ${startingPos}`)
console.log(`Second Value ${nextPos}`)
console.log(`Target ${target}`)
// A match has been found
return [nums.indexOf(startingPos), nums.lastIndexOf(nextPos)];
} else{
// Move to next number if index 1 is not eql
// nextPos++;
let nextPosIndex = nums[inc];

nextPos = nums[inc];
console.log(`Values [${startingPos}], [${nextPos}]`)
console.log("No Matches");
// Increment the next value to check
inc++;
// Reset loop if no match is found from 2nd position
if(x == (nums.length - 1)){
// Increment the initial value in first pos
intVal++;
startingPos = nums[intVal];
// Reset values to check new numbers
x = 0;
inc = 1;
} 
// check if we exhausted all options
if(startingPos === undefined){
return "No Matches.";
}
}

}
};
twoSum([5, 2, 5, 5, 1, 3, 6, 8, 4, 3, 2, 7], 14)

——在处理更多的问题之前，我恐怕会陷入选择最不合逻辑的解决问题方式的怪圈。

如何修改此问题以快速检查两个值是否等于目标?

下面是一个编译器的实例:https://replit.com/@FPpl/safeheartfeltarchitect# index.js

Answer 1

当对一个数字进行迭代时，如果该值与目标值的sum匹配，则可以将其放入集合中(使用O(1)查找)。例如，如果对数字5进行迭代，而目标是20，则将15放入集合中。

在迭代过程中，如果要迭代的数字在集合中已经存在，则与先前找到的数字匹配，并且可以返回两个索引。

const twoSum = function(nums, target) {
// For this Map, the key is the number which, if found again, is a match
// eg, if target is 20, and the number 5 is iterated over
// the key will be 15
// The value is the index of the prior number found - eg, index of 5
const valuesAlreadyFound = new Map();
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
if (valuesAlreadyFound.has(num)) {
// We have a match, get both indicies:
console.log('Match for values', target - num, num);
return [valuesAlreadyFound.get(num), i];
}
// This wasn't a match. Identify the number which, when paired, is a match
const matchNeeded = target - num;
valuesAlreadyFound.set(matchNeeded, i);
}
return 'No match';
};
console.log('Indicies found:', twoSum([5, 2, 5, 5, 1, 3, 6, 8, 4, 3, 2, 7], 14));