arrays - 在 O(n*log(n)) 中找到一对具有给定和和乘积的数组元素

Question

令 A 为 n 个正整数数组，k 为给定整数。

我正在寻找算法来查找数组中是否有一对元素使得 A[i] * A[j] == k 和 A[i] == A[j] + k。如果存在这样的一对，算法应该返回它们的索引。

这是一个家庭作业，我们被告知有一个 O(n*log(n)) 的解决方案。

Answer 1

首先想到的是:

Make a Map<Integer, Integer>

for each number a in A:
   if (k / a) is a key in the HashMap:
      output the index of a, and HashMap.get(k/a)
   else
      HashMap.add(a, indexof(a))

所以遍历数组是 O(n)，在 Map 中查找键是 O(log n)(假设你使用了 TreeMap，HashMap 在最好的情况下可能更好，但在最坏的情况下更差)

编辑:我想这只能回答 a) 但你明白了