algorithm - 将一个非常简单的 O(n^3) 算法优化为 O(n^2) 算法。

Question

这个问题我纠结了很久。令 X、Y 和 Z 为 n 个整数的集合。令 k 为任何整数。问题“你能在 X 中找到 x，在 Y 中找到 y，在 Z 中找到 z 使得 x + y + z = k”显然可以通过尝试所有组合在 O(n^3) 时间内解决。给出一个在 O(n^2) 中运行的算法。您可以假设 sort 是一个内置方法，运行时间为 O(n*log n)。这是一个旧测试的问题。任何帮助将不胜感激。谢谢。

Answer 1

Any help will be appreciated.

我的帮助以提示的形式出现。

提示:

1 - 如果 x + y + z == k，则 z = k - x - y ...

2 - 如何在 O(1) 中测试集合成员资格？ (忽略了问题中的提示......)

或

2a - 当 N 是 M * M 时，O(N log N) 是什么？ (为什么我选择 O(N log N) ??)