您的代码需要一个数字数组和一个目标数字/总和。然后,它返回数组中两个数字的索引,这两个数字的总和达到目标数字/总和。
考虑一个数字数组,例如[1, 2, 3]
和一个目标5
。你的任务是找到这个数组中的两个数字,将其相加5
。解决这个问题的一种方法是循环遍历数组中的每个数字并问自己“是否有一个数字(我已经在数组中看到过),我可以将其添加到当前数字中以获得我的值”target
sum?".
好吧,如果我们循环示例数组[1, 2, 3]
我们首先从索引 0 开始,编号为1
。目前,我们还没有看到可以添加的数字1
达到我们的目标5
因为我们还没有循环任何数字。
所以,到目前为止,我们已经遇到了这个数字1
,位于索引处0
。这存储在哈希图(即对象)中:{'1': 0}
。其中键是数字和值 (0
) 是它被看到的索引。该对象的目的是存储我们看到的数字以及它们出现的索引。
接下来,继续循环到索引 1,当前编号为2
。现在我们可以问自己一个问题:是否有一个我已经在数组中看到的数字可以添加到我当前的数字中2
得到目标总和5
。可以通过以下方式获得达到目标所需添加到当前数字的金额target-currentNumber
。在这种情况下,我们目前正在2
,所以我们需要添加3
达到我们的目标总和 5。使用 hashmap/object,我们可以检查我们是否已经看到了这个数字3
。为此,我们可以尝试访问该对象3
关键是做obj[target-currentNumber]
。目前,我们的对象只有以下键'1'
,所以当我们尝试访问3
你会得到的钥匙undefined
。这意味着我们还没有看到这个数字3
然而,到目前为止,我们还没有什么可以添加的2
得到我们的target
sum.
所以现在我们的对象/哈希图看起来像{'1': 0, '2': 1}
,正如我们看到的数字1
位于索引处0
,我们已经看到了这个数字2
位于索引处1
.
最后,我们到达数组中位于索引 2 处的最后一个数字。数组的索引 2 保存该数字3
。现在,我们再次问自己这个问题:是否有一个我们已经看到的数字可以添加到其中3
(我们当前的号码)以获得target
和?。我们需要添加的号码3
以获得我们的目标数量5
is 2
(通过做得到target-currentNumber
)。我们现在可以检查我们的对象,看看我们是否已经看到了一个数字2
在数组中。为此,我们可以使用obj[target-currentNumber]
获取存储在键中的值2
,它存储索引 1。这意味着数字2
数组中确实存在,因此我们可以将其添加到3
达到我们的目标。由于该值位于对象中,因此我们现在可以返回我们的发现。这是所见数字发生位置的索引,以及当前数字的索引。
一般来说,该对象用于跟踪数组中所有先前看到的数字,并保留看到该数字的索引值。
这是运行代码的示例。它返回[1, 2]
,作为索引处的数字1
and 2
可以相加得到目标总和5
:
const twoSum = function(nums, target) {
const hash = {}; // Stores seen numbers: {seenNumber: indexItOccurred}
for (let i = 0; i < nums.length; i++) { // loop through all numbers
const n = nums[i]; // grab the current number `n`.
if (hash[target - n] !== undefined) { // check if the number we need to add to `n` to reach our target has been seen:
return [hash[target - n], i]; // grab the index of the seen number, and the index of the current number
}
hash[n] = i; // update our hash to include the. number we just saw along with its index.
}
return []; // If no numbers add up to equal the `target`, we can return an empty array
}
console.log(twoSum([1, 2, 3], 5)); // [1, 2]
A solution like this might seem over-engineered. You might be wondering why you can't just look at one number in the array, and then look at all the other numbers and see if you come across a number that adds up to equal the target
. A solution like that would work perfectly fine, however, it's not very efficient. If you had N numbers in your array, in the worst case (where no two numbers add up to equal your target
) you would need to loop through all of these N numbers - that means you would do N iterations. However, for each iteration where you look at a singular number, you would then need to look at each other number using a inner loop. This would mean that for each iteration of your outer loop you would do N iterations of your inner loop. This would result in you doing N*N or N2 work (O(N2) work). Unlike this approach, the solution described in the first half of this answer only needs to do N iterations over the entire array. Using the object, we can find whether or not a number is in the object in constant (O(1)) time, which means that the total work for the above algorithm is only O(N).
有关对象如何工作的更多信息,您可以阅读括号表示法和其他属性访问器方法here https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Property_accessors#Bracket_notation.