二和 Leetcode 解释、Hashmap、Javascript [英] Two-sum Leetcode explanation, Hashmap, Javascript

问题描述

我只是想知道谁能一步一步解释这个解决方案的算法.我不知道哈希图是如何工作的.你能否也给我一个使用哈希图的基本例子来理解这个算法.谢谢！

Im just wondering who can explain the algorithm of this solution step by step. I dont know how hashmap works. Can you also give a basic examples using a hashmap for me to understand this algorithm. Thank you!

var twoSum = function(nums, target) {
  let hash = {};

  for(let i = 0; i < nums.length; i++) {
    const n = nums[i];
    if(hash[target - n] !== undefined) {
      return [hash[target - n], i];
    }
    hash[n] = i;
  }
  return [];
}

推荐答案

您的代码采用一个数字数组和一个目标数字/总和.然后它返回数组中两个数字的索引，这两个数字相加为目标数字/总和.

Your code takes an array of numbers and a target number/sum. It then returns the indexes in the array for two numbers which add up to the target number/sum.

考虑一个数字数组，例如 [1, 2, 3] 和 5 的目标.你的任务是在这个数组中找到添加到 5 的两个数字.解决此问题的一种方法是遍历数组中的每个数字并问自己是否有一个数字(我已经在我的数组中看到)可以添加到当前数字以获得我的 target总和?".

Consider an array of numbers such as [1, 2, 3] and a target of 5. Your task is to find the two numbers in this array which add to 5. One way you can approach this problem is by looping over each number in your array and asking yourself "Is there a number (which I have already seen in my array) which I can add to the current number to get my target sum?".

好吧，如果我们遍历 [1, 2, 3] 的示例数组，我们首先从索引 0 开始，编号为 1.目前，我们已经看到没有数字可以添加到 1 来获得我们的目标 5 因为我们还没有循环任何数字.

Well, if we loop over the example array of [1, 2, 3] we first start at index 0 with the number 1. Currently, there are no numbers which we have already seen that we can add with 1 to get our target of 5 as we haven't looped over any numbers yet.

所以，到目前为止，我们遇到了编号 1，它位于索引 0 处.这以 {'1': 0} 的形式存储在 hashmap(即对象)中.其中键是数字，值 (0) 是看到它的索引.该对象的目的是存储我们看到的数字以及它们出现的索引.

So, so far, we have met the number 1, which was at index 0. This is stored in the hashmap (ie object) as {'1': 0}. Where the key is the number and the value (0) is the index it was seen at. The purpose of the object is to store the numbers we have seen and the indexes they appear at.

接下来，循环继续索引 1，当前编号为 2.我们现在可以问自己一个问题:是否有一个我已经在我的数组中看到的数字可以添加到我当前的 2 数字中以获得 5.可以通过执行target-currentNumber来获得要添加到当前数字才能到达目标所需的数量.在这种情况下，我们当前在 2，所以我们需要添加 3 以达到我们的目标总和 5.使用 hashmap/object，我们可以检查我们是否已经看到数字 3.为此，我们可以尝试通过执行 obj[target-currentNumber] 来访问对象 3 键.目前，我们的对象只有 '1' 键，所以当我们尝试访问 3 键时，您会得到 undefined.这意味着我们还没有看到数字 3，所以到目前为止，我们还没有任何东西可以添加到 2 来获得我们的 target 总和.

Next, the loop continues to index 1, with the current number being 2. We can now ask ourselves the question: Is there a number which I have already seen in my array that I can add to my current number of 2 to get the target sum of 5. The amount needed to add to the current number to get to the target can be obtained by doing target-currentNumber. In this case, we are currently on 2, so we need to add 3 to get to our target sum of 5. Using the hashmap/object, we can check if we have already seen the number 3. To do this, we can try and access the object 3 key by doing obj[target-currentNumber]. Currently, our object only has the key of '1', so when we try and access the 3 key you'll get undefined. This means we haven't seen the number 3 yet, so, as of now, there isn't anything we can add to 2 to get our target sum.

所以现在我们的对象/哈希图看起来像 {'1': 0, '2': 1}，因为我们看到了索引处的数字 10，我们已经看到索引 1 处的数字 2.

So now our object/hashmap looks like {'1': 0, '2': 1}, as we have seen the number 1 which was at index 0, and we have seen the number 2 which was at index 1.

最后，我们到达了数组中的最后一个数字，即索引 2.数组的索引 2 包含数字 3.现在，我们再次问自己一个问题:是否有一个我们已经看到的数字可以添加到 3(我们当前的数字)以获得 target 总和?我们需要添加到 3 以得到 5 的目标编号是 2 (通过执行 target-currentNumber).我们现在可以检查我们的对象，看看我们是否已经在数组中看到了一个数字 2.为此，我们可以使用 obj[target-currentNumber] 来获取存储在键 2 处的值，该键存储 1 的索引.这意味着数字 2 确实存在于数组中，因此我们可以将其添加到 3 以达到我们的目标.由于值在对象中，我们现在可以返回我们的发现.那是看到的数字出现的索引，以及当前数字的索引.

Finally, we reach the last number in your array which is at index 2. Index 2 of the array holds the number 3. Now again, we ask ourselves the question: Is there a number we have already seen which we can add to 3 (our current number) to get the target sum?. The number we need to add to 3 to get our target number of 5 is 2 (obtained by doing target-currentNumber). We can now check our object to see if we have already seen a number 2 in the array. To do so we can use obj[target-currentNumber] to get the value stored at the key 2, which stores the index of 1. This means that the number 2 does exist in the array, and so we can add it to 3 to reach our target. Since the value was in the object, we can now return our findings. That being the index of where the seen number occurred, and the index of the current number.

一般来说，该对象用于跟踪数组中所有以前看到的数字，并保留看到该数字的索引值.

In general, the object is used to keep track of all the previously seen numbers in your array and keep a value of the index at which the number was seen at.

这是运行代码的示例.它返回 [1, 2]，因为索引 1 和 2 处的数字可以相加得到 的目标总和5:

Here is an example of running your code. It returns [1, 2], as the numbers at indexes 1 and 2 can be added together to give the target sum of 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]

这样的解决方案可能看起来设计过度.您可能想知道为什么不能只查看数组中的一个数字，然后查看所有其他数字，看看您是否遇到了一个加起来等于 target 的数字.这样的解决方案可以很好地工作，但是，它不是很有效.如果您的数组中有 N 个数字，在最坏的情况下(没有两个数字加起来等于您的 target)，您需要遍历所有这些 N 个数字 - 这意味着您将进行 N 次迭代.但是，对于您查看单数的每次迭代，您都需要使用内部循环查看其他数字.这意味着对于您的外循环的每次迭代，您都会对您的内循环进行 N 次迭代.这将导致您进行 N*N 或 N² 工作(O(N²) 工作).与这种方法不同，本答案前半部分描述的解决方案只需要对整个数组进行 N 次迭代.使用对象，我们可以在常数(O(1))时间内找到一个数字是否在对象中，这意味着上述算法的总工作量只有O(N).

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 N² work (O(N²) 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).

有关对象如何工作的更多信息，您可以阅读括号表示法和其他属性访问器方法 这里.

For further information about how objects work, you can read about bracket notation and other property accessor methods here.

这篇关于二和 Leetcode 解释、Hashmap、Javascript的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！