两和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 的数字。解决此问题的一种方法是循环遍历数组中的每个数字，然后问自己是否有一个数字（我已经在数组中看到了），可以将其添加到当前数字中以获得我的目标总和？。

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} 的形式存储在哈希图中（即对象）。其中的键是数字，值（ 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.

接下来，循环继续索引1，当前数字为 2 。现在我们可以问自己一个问题：是否有一个我已经在数组中看到的数字，可以将其加到当前的 2 数中，以获得 5 。通过执行 target-currentNumber 可以获取添加到当前数字以达到目标所需的金额。在这种情况下，我们当前使用的是 2 ，因此我们需要添加 3 才能达到目标金额。使用哈希图/对象，我们可以检查是否已经看到数字 3 。为此，我们可以尝试通过执行 obj [target-currentNumber] 来访问对象 3 键。当前，我们的对象仅具有'1'的密钥，因此当我们尝试访问 3 密钥时，会得到 undefined 。这意味着我们还没有看到数字 3 ，所以，到目前为止，它们还不能添加到 2 来获取目标 的总和。

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. 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, their isn't anything we can add to 2 to get our target sum.

现在我们的对象/哈希图看起来像 {'1'：0，'2'：1} ，因为我们已经看到索引为<$ c的数字 1 $ c> 0 ，我们已经看到数字 2 在索引 1 。

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 （我们当前的数字）中以获得目标金额？我们需要加到 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/hashmap 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 hashmap, 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 hashmap/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:

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 [];
}

console.log(twoSum([1, 2, 3], 5));

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

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

编辑：当您询问对象的其他示例/用途/哈希图时，这里有一些

As you asked for further examples/usages of objects/hashmaps here are some examples.

一个对象的一些简单用例是存储键值对。为了真正简化它，您可以将对象/哈希图视为数组，但是可以使用命名索引代替索引（即数字）。例如，您可能有一个看起来像这样的数组：

Some simple use cases for an object is to store key-value pairs. To really simplify it, you can think of an object/hashmap as being an array, however, instead of indexes (so numbers), you can have "named" indexes. For example, you could have an array which looks like so:

//                 0      1   2   3
const person = ["James", "A", 18, 3];

上面，我们有一个人员数组，其中包含有关 person的信息。在索引 0 下，我们有此人的名字，在索引 1 下，我们有姓的首字母，在索引 2 我们有这个人的年龄，在指数 3 我们有这个人的家庭成员人数。这种代表一个人的方法不是很友善，因为您必须记住每个索引包含哪些信息。并非总是容易猜到的，尤其是当它们包含数字时。因此，我们可以使用一个对象表示一个人。从本质上讲，这可以使我们命名索引（这些命名索引称为键）。因此，使用上面的数组，我们可以做类似的事情来将我们的 person 表示为一个对象：

Above, we have a person array which holds information about a person. At index 0 we have the name of the person, at index 1 we have the last name initial, at index 2 we have the age of the person and at index 3 we have the number of family members that person has. This way of representing a single person isn't very friendly, as you have to remember what information each index holds. It's not always easy to guess, especially if they hold numbers. So, instead, we can represent a single person using an object. This essentially allows us to name our indexes (these named indexes are known as keys). So using an array above, we can do something like so to represent our person as an object:

const person = {
  name: "James",
  surname_initial: "A",
  age: 18,
  familyMembers: 3
}

现在可以访问以 name ，则可以使用方括号（ person [ name] 给出 James）或点表示法（ person.name 还给出了 James），以得到 James 的值。这样做可以使您清楚地定义每个数据是什么。

Now to access the data held at name, you can use bracket notation (person["name"] gives "James") or dot notation (person.name also gives "James") to get the value of "James". Doing this allows you to clearly define what each piece of data is.

关于对象的好处是它们只能保留唯一的键。如果您尝试设置密钥，例如 person [ age] = 30 ，那么您将进行更新 age 键将其值设置为 30 。它不会创建两个名称为 age 的 keys ，而是会更新密钥 age的值更改为 30 的新值。因此，对象可以很好地处理诸如分组或查找唯一值之类的事情。

The good thing about objects is that they can only keep unique keys. If you try and set a key, for instance person["age"] = 30, then you'll update the age key to have a value of 30. It won't create 2 keys with the name of age, instead, it will update the value at the key age to the new value of 30. So, objects can be good for dealing with things such as grouping or finding unique values.

对象的另一种用例可能是对项目中出现的频率进行计数数组。例如，如果您有数组 ['a'，'b'，'a'，'a'，'b'，'c'] ，要求找到多少'a' s，'b' s和'c' 出现在数组中，您可以为此使用一个对象。主要思想是遍历数组并检查对象，以查看当前项是否已成为对象中的键。如果是，那么您可以增加它所持有的计数器，如果它不在您的对象中，则可以将新键设置为当前项，其值设置为 1 表示到目前为止，您仅看到了其中一项。可以这样实现：

Another use case for objects could be to keep a count for the frequency of items in an array. For example, if you had the array ['a', 'b', 'a', 'a', 'b', 'c'], and you were asked to find how many 'a's, 'b's and 'c's appear in the array, you can use an object for this. The main idea is the loop over your array and check your object to see if the current item is already a key in your object. If it is, then you can increment the counter which it holds, if it isn't in your object you can set a new key to be the current item, with a value set to 1, to indicate that so far you have only seen one of that item. This can be achieved like so:

const arr = ['a', 'b', 'a', 'a', 'b', 'c'];

const freq = {};

for(let i = 0; i < arr.length; i++) {
  const currentItem = arr[i];
  if(freq[currentItem]) { // if currentItem is a key in the freq object
    freq[currentItem] = freq[currentItem] + 1; // update the currentItems counter value to be incremented
  } else { // if the currentItem is not a key in the freq object
    freq[currentItem] = 1; // set a new key to be the value of `currentItem`, and initialize its counter to `1`.
  }
}
console.log(freq); // Output the freq object to see frequency.

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