两个重复的和

Question

我一直在研究二和问题：

给定一个整数数组，返回两个数字的索引，使它们相加达到特定目标。

我对允许重复的变化感到困惑。如果有重复，为什么会出现问题呢？我们不能只返回重复项的索引吗？

Answer 1

为了向其他人澄清，“重复变体”正是您所期望的：数字可能在数组中重复。

如果您编写暴力算法，这并不重要。

但通常的非暴力算法涉及将数字散列到其索引（即创建反向数组）。这样，给定一个目标T，就检查 whecks 是否T - Array[0]作为散列键存在（在这种情况下，已找到解决方案），如果不存在，则继续T - Array[1]，依此类推。

现在，如果所有数字都是唯一的，则上述方法有效。但是，如果数字可以重复，则存在这种情况，例如：

Array[] = {1, 3, 4, 4, 6, 8};
T = 8;

哈希必须包含 4 的一对多映射。因此，它涉及确保您不会意外地从同一元素创建两次总和，例如

Array[2] + Array[2]