问题描述
4-SUM 如下:
给定一个包含 N 个不同整数的数组，找出 4 个整数 a、b、c、d，使得 a+b+c+d = 0.
对于 3-SUM 问题，我可以提出使用二次算法的三次算法.对于 4-SUM，我们可以做得比三次更好吗?
I could come up with a cubic algorithm using quadratic algorithm for 3-SUM problem. Can we do better than cubic for 4-SUM?
推荐答案
是的，你可以.查看所有数字对并存储它们的总和(并存储哪些数字给出该总和).之后，为每个总和检查是否在您拥有的总和中找到它的否定.使用散列可以达到二次复杂度，使用 std::map 可以达到 O(n^2*log(n)).
Yes you can. Go over all pairs of numbers and store their sum(and also store which numbers give that sum). After that for each sum check if its negation is found among the sums you have. Using a hash you can reach quadratic complexity, using std::map, you will reach O(n^2*log(n)).
为了确保没有多次使用数字，最好存储索引而不是每个总和的实际数字.此外，由于给定的总和可能由不止一对形成，因此您将不得不使用哈希多重映射.请记住，对于总和 X = a1 + a2 的数字是不同的，总和 -X 最多可以使用 a1 形成一次，并且一次使用 a2 所以对于给定的总和 X 您将不得不迭代最多 3 对，将 -X 作为总和.这仍然是恒定的.
to make sure no number is used more than once it will better to store indices instead of the actual numbers for each sum. Also as a given sum may be formed by more than one pair, you will have to use a hash multimap. Having in mind the numbers are different for a sum X = a1 + a2 the sum -X may be formed at most once using a1 and once using a2 so for a given sum X you will have to iterate over at most 3 pairs giving -X as sum. This is still constant.
这篇关于4-SUM 的二次算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！