下面我列出了一个我遇到麻烦的问题。这个问题是一个远离 O(n^2) 解决方案的简单嵌套循环，但我需要它是 O(n)。任何想法应该如何解决？是否有可能形成两个方程？
给定一个整数数组 A，检查是否有两个索引 i 和 j 使得 A[j] = 2∗A[i]。例如，在数组 (25, 13, 16, 7, 8) 上，算法应该输出“true”（因为 16 = 2 * 8），而在数组 (25, 17, 44, 24) 上，算法应该输出“错误的”。描述这个问题的算法，其最坏情况下的运行时间优于 O(n^2)，其中 n 是 A 的长度。
谢谢！
这是使用哈希表的好地方。创建一个哈希表并将数组中的每个数字输入到哈希表中。然后，再次遍历数组并检查每个 i 的哈希表中是否存在 2*A[i]。如果是这样，那么您知道该属性存在一对索引。如果没有，您就知道不存在这样的一对。
按照预期，这需要 O(n) 时间，因为哈希表上的 n 次操作需要预期的摊销 O(1) 时间。
希望这可以帮助！
templatetypedef 建议使用哈希表是一个很好的建议。我想解释一下为什么。
这里的关键是意识到您实际上是在寻找集合中的某些值。您有一组要搜索的数字（ 2 * 输入数组中的每个值）和一组要搜索的数字（输入数组中的每个值）。您的蛮力天真案例只是直接在搜索数组中查找值。您想要做的是将您的“搜索”集预加载到比数组（如哈希表）查找速度更快的东西中，然后您可以从那里进行搜索。
您还可以通过不搜索奇怪的A[i]位置来进一步修剪结果；A[i]因为你知道，如果是奇怪的，那A[i] = 2 * A[j]永远不会是真的。A[i]您还可以在初始化期间动态计算“搜索”数组中的最小值和最大值，并修剪A[i]该范围之外的所有值。
那里的性能很难用大 O 形式表达，因为它取决于数据的性质，但您也可以计算最佳和最坏情况以及摊销情况。
但是，正确选择哈希表大小（如果您的值范围很小，您可以简单地选择一个大于您的值范围的容量，其中哈希函数就是值本身）实际上可能会在某些情况下使修剪成本更高，您必须对其进行分析才能找到答案。