二和 Leetcode 解释、Hashmap、Javascript

Question

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

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

Answer 1

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

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

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

所以，到目前为止，我们已经遇到了1在 index 处的 number 0。这作为 .hashmap（即对象）存储在哈希图中{'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总和。

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

最后，我们到达数组中索引 2 处的最后一个数字。数组的索引 2 保存数字3。现在，我们再问自己一个问题：是否有一个我们已经看到的数字可以添加到3（我们当前的数字）上以获得target总和？。我们需要添加的3数字5是2（通过执行 获得target-currentNumber）。我们现在可以检查我们的对象，看看我们是否已经2在数组中看到了一个数字。为此，我们可以使用obj[target-currentNumber]获取存储在 key 中的值2，它存储索引 1。这意味着该数字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 ²工作（O(N ² ) 工作）。与这种方法不同的是，本答案前半部分描述的解决方案只需要对整个数组进行N次迭代。使用对象，我们可以在常数（O（1））时间内找到对象中是否有数字，这意味着上述算法的总工作量仅为O（N）。

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

编辑：正如您要求的对象/哈希图的进一步示例/用法，这里有一些示例。

对象的一些简单用例是存储键值对。为了真正简化它，您可以将对象/哈希图视为一个数组，但是，您可以拥有“命名”索引而不是索引（即数字）。例如，您可以有一个如下所示的数组：

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

上面，我们有一个 person 数组，其中包含有关 a 的信息person。在索引中0我们有这个人的名字，在索引中1我们有姓氏的首字母，在索引中2我们有这个人的年龄，在索引中我们有这个人3的家庭成员数量。这种表示单个人的方式不是很友好，因为您必须记住每个索引包含哪些信息。猜测并不总是那么容易，特别是如果他们持有数字。因此，相反，我们可以使用一个对象来表示一个人。这基本上允许我们命名我们的索引（这些命名的索引被称为键）。所以使用上面的数组，我们可以做类似这样的事情来将我们的表示person为一个对象：

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

现在要访问保存在 的数据name，您可以使用括号表示法（person["name"]给出“James”）或点表示法（person.name也给出“James”）来获取 的值"James"。这样做可以让您清楚地定义每条数据是什么。

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

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

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