Leetcode：二和的直观方法

想象一下，您是 Spot-On Change 酒店内一家纪念品商店的骄傲老板。当您关闭收银机时，您发现多出了 8 欧元。似乎一位客人没有收到正确的零钱。这可能会损害酒店的声誉。为了避免这种情况，您决定解决错误零钱的谜团。打开商店的现金系统后，您发现错误发生在两个不同的账户上！

你制定了一个计划：走访每个房间，询问客人在商店里收到了多少零钱，直到找到两个拿错钱的人。到达一楼后，一位客人说收到了 4 欧元的零钱。你计算出需要找到一个数字，将其与 4 欧元相加，结果是 8。移至二楼，客人的零钱是 5 欧元。4 + 5 结果是 9，所以不可能是这个……五楼、六楼……十楼，不，不，不！

由于第一次尝试没有找到值，你下到二楼，再次开始询问所有客人的零钱，以便将其与下一层起始楼层的值进行比较，这很累人，不是吗？在计算机科学中，这种搜索方法称为蛮力搜索，这是一种非常慢的搜索方法，通过将一个项目与数组中的后续项目进行比较来工作。

这浪费了大量的时间，而且效率不高，想象一下在 Spot-On Change Hotel 的所有楼层上下好几次！这对您来说不切实际，对计算机来说也不切实际。

如果你好奇在软件程序中这种上下移动是如何实现的，那么在 JavaScript 中它看起来应该是这样的：

 twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] === target) { return [i, j]; } } } }

冷静评估情况后，您意识到有更有效的方法来找到两位拿错零钱的客人。

你完善了最初的数学直觉，即 9 欧元等于 x + y。通过一些算术运算，你意识到：x + y = 9 与 y = 9 — x 相同，这对提高搜索效率大有裨益。

你的策略中另一个改变是，现在你会拿一个记事本记下客人告诉你的数值，这样你就不用为客人问两次同样的数值，也不用花一整天的时间上下楼梯了。（电梯坏了那该有多可怕啊！）。

有了新工具后，您前往一楼，一位客人告诉您，他们有 5 欧元的零钱。您将其记录为 {5: 0}，表示位置 0 的值为 5。在等式中用 5 代替 x，计算出 y = 8–5，结果为 y = 3。由于您的记事本仍为空，因此您没有记录数字 3，而 3 是 5 的补数，可得出结果 8。然后，您将数字 5 写在记事本上（请记住，始终写下当前验证的数字，而不是其补数；您只会使用补数将其与您写下的目标数字进行比较）。您继续与第二位客人交谈，他提到收到 2 欧元的零钱。再次应用公式：y = 8–2 => y = 6，您检查记录，没有找到任何数字 6。因此，您将 2 添加到记录中，现在记录为 {5: 0, 2: 1}。继续搜索，下一位客人报告收到 3 欧元的零钱。您再次计算：y = 8–3 => y = 5。Bingo！您的记事本上记录了 5！来自 0 楼的客人与来自 2 楼的客人互补！这种方法称为哈希表，对您和计算机来说，它都更快、更高效。在 JavaScript 中，这将按如下方式实现：

 twoSum(nums, target) { const myTable = {}; for (let i = 0; i < nums.length; i++) { const complementaryNumber = target - nums[i]; if (complementaryNumber in myTable) { return [i, myTable[complementaryNumber]]; } myTable[nums[i]] = i; } }

这是一道Leetcode上的简单问题，只有在理解了背后的概念后才会变得简单。我建议您尝试自己解决这个问题，花一些时间尝试建立背后的直觉，创建自己的类比，复习，并尝试编写伪代码，然后再继续解决问题。

我希望我的类比能帮助您更好地理解二和挑战背后的概念。

下次再见！