时间戳

首页 > 解决方案 > 二和 Leetcode 解释、Hashmap、Javascript

javascript - 二和 Leetcode 解释、Hashmap、Javascript

问题描述

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

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

标签： javascriptalgorithmhashmap

解决方案

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

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

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

所以，到目前为止，我们已经遇到了1index 处的数字0。这存储在哈希图（即对象）中作为{'1': 0}. 其中键是数字，值 ( 0) 是看到它的索引。该对象的目的是存储我们看到的数字和它们出现的索引。

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

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

最后，我们到达数组中的最后一个数字，即索引 2。数组的索引 2 保存数字3。现在，我们再次问自己一个问题：是否有一个我们已经看到的数字可以添加到3（我们当前的数字）以获得target总和？我们需要添加来3获得目标数量的数字5是2（通过do获得target-currentNumber）。我们现在可以检查我们的对象，看看我们是否已经2在数组中看到了一个数字。为此，我们可以使用obj[target-currentNumber]存储在 key 中的值，该值存储21 的索引。这意味着该数字2确实存在于数组中，因此我们可以将其添加到3达到我们的目标。由于值在对象中，我们现在可以返回我们的发现。那是所见数字发生位置的索引，以及当前数字的索引。

通常，该对象用于跟踪数组中所有先前看到的数字，并保留看到该数字的索引值。

这是运行代码的示例。它返回[1, 2], 作为索引处的数字，1并且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]

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

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

推荐阅读