java - A[j] = 2∗A[i] in list with better than O(n^2) runtime

Question

下面我列出了我遇到的一些问题。这个问题是一个远离 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 的长度。

谢谢!

Answer 1

这是使用哈希表的好地方。创建一个哈希表，并将数组中的每个数字输入到哈希表中。然后，再次遍历数组并检查每个 i 的哈希表中是否存在 2*A[i]。如果是这样，那么您就知道该属性存在一对索引。如果不是，则您知道不存在这样的对。

按预期，这需要时间 O(n)，因为哈希表上的 n 次操作需要平均分摊的 O(1) 时间。

希望这对您有所帮助!