4个数组中4个整数的和
4个数组中4个整数的和
提问于 2016-11-13 15:09:38
给定整数值的四个列表A，B，C，D，计算出有多少元组(i，j，k，l)使得Ai + Bj + Ck + Dl为零。
为了使问题更容易解决，所有的A，B，C，D都有相同长度的N，其中0≤N≤500。所有整数都在-228到228 - 1之间，并且保证结果最多为231 -1。
示例：
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]产出:2
说明:这两个元组是：
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0我刚想出了一个把所有向量连在一起的解决方案，然后找出4和。但我知道有更好的解决办法。有人能解释一下更好的解决方案吗？我只看到了使用O(N^2)的代码，但我无法理解。
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-11-13 15:34:08
这是我的O(n^2)解决方案：
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
int n = A.size();
int result = 0;
unordered_map<int,int> sumMap1;
unordered_map<int,int> sumMap2;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
int sum1 = A[i] + B[j];
int sum2 = C[i] + D[j];
sumMap1[sum1]++;
sumMap2[sum2]++;
}
}
for(auto num1 : sumMap1) {
int number = num1.first;
if(sumMap2.find(-1 * number) != sumMap2.end()) {
result += num1.second * sumMap2[-1 * number];
}
}
return result;
}核心观察是-如果W + X + Y + Z = 0那么W + X = -(Y + Z)。
这里，我在(A，B)和(C，D)中对每个可能的和使用了两个哈希表，查找了这个和出现的次数。
然后，对于每个sum(A, B)，我们可以发现sum(C, D)是否包含保证sum(A, B) + sum(C, D) = 0的免费和。将(sum(a, b)的出现次数)*(免费sum(c,d)的次数)添加到结果中。
创建sum(A, B)和sum(C, D)将花费O(n^2)时间。计算元组的数量是O(n^2)，因为每个对都有n^2和(A-B，C-D)。其他操作，如对哈希表的插入和搜索，是摊销的O(1)。因此，总的时间复杂度是O(n^2)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/40575323
复制相关文章
相似问题
腾讯云开发者
