问题描述
四SUM如下：给定N的阵列的不同整数找到4整数a ,, B，C，D，使得A + B + C + D = 0。我能想出使用二次算法3和问题立方算法。我们能为4-SUM做的比立方好？
The 4-SUM is as follows:Given an array of N distinct integers find 4 integers a,,b,c,d such that a+b+c+d = 0.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 ::地图，你会到达为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)).
编辑：以确保没有号码多次使用它会更好地存储索引，而不是实际数字为每个总和。另外，作为一个给定的和可以由一个以上的对来形成，则必须使用一个散列multimap中。铭记的数字是一笔 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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！