4-SUM如下:给定N个不同整数的数组找到4个整数a,b,c,d使得a + b + c + d = 0.我可以使用二次算法得到一个三次算法3-SUM问题.对于4-SUM,我们能做的比立方更好吗？
izo*_*ica 16
是的你可以.遍历所有数字对并存储它们的总和(并且还存储哪些数字给出该总和).之后,每次总结检查是否在您所拥有的金额中找到了否定.使用散列可以达到二次复杂度,使用std :: map,您将达到O(n^2*log(n)).
编辑:为了确保不会多次使用数字,最好存储索引而不是每个总和的实际数字.另外,由于给定的总和可能由多个对形成,因此您必须使用散列多图.考虑到数字是不同的总和X = a1 + a2,总和-X最多可以形成一次使用a1,一旦使用,a2所以对于给定的总和,X你将不得不迭代最多3对-X作为总和.这仍然是不变的.
对于使用O(N ^ 2)额外存储器的该问题,还存在O(N ^ 2)算法.
1-生成O(N ^ 2)中的所有成对和并将对(a_i,a_j)存储在哈希表中,并使用它们的和的绝对值作为哈希表的键(a_i和a_j是两个不同的数字)输入数组)
2-迭代表,找到一个具有四个独特元素的负和正和的键,返回作为答案
如果您不想使用哈希表,还有另一种选择.由于您的数字是整数,您可以使用类似基数排序(总和列表中有O(N ^ 2)个元素)对总和列表中元素的线性时间内的所有总和列表进行排序.