个人工作室经营范围,泰安搜索引擎优化招聘,上海缪斯设计公司,网站项目建设与管理论文题目
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) #xff0c;使得 A[i] B[j] C[k] D[l] 0。 为了使问题简单化#xff0c;所有的 A, B, C, D 具有相同的长度 N#xff0c;且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间使得 A[i] B[j] C[k] D[l] 0。 为了使问题简单化所有的 A, B, C, D 具有相同的长度 N且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间最终结果不会超过 231 - 1 。
思考
这一题和LeetCode 18. 四数之和题目相似但是本质不同。 因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的很有多细节需要处理。 而本题是四个独立的数组只要找到A[i] B[j] C[k] D[l] 0就可以不用考虑有重复的四个元素相加等于0的情况。 回顾之前的两数之和其实这边思路是一致的。 采用分为两组HashMap存一组另一组和HashMap进行比对。 这样的话情况就可以分为三种 1.HashMap存一个数组如A。然后计算三个数组之和如BCD。时间复杂度为O(n)O(n3),得到O(n3). 2.HashMap存三个数组之和如ABC。然后计算一个数组如D。时间复杂度为O(n3)O(n),得到O(n3). 3.HashMap存两个数组之和如AB。然后计算两个数组之和如CD。时间复杂度为O(n2)O(n2),得到O(n^2). 三.根据第二点我们可以得出要存两个数组算两个数组。 四.我们以存AB两数组之和为例。首先求出A和B任意两数之和sumAB以sumAB为keysumAB出现的次数为value存入hashmap中。 然后计算C和D中任意两数之和的相反数sumCD在hashmap中查找是否存在key为sumCD。 这段理解来自于guo-sheng-fei 觉得说的挺有条理直接拿过来用了。 代码
class Solution {
public:int fourSumCount(vectorint A, vectorint B, vectorint C, vectorint D) {//前面是nums,后面是出现的频次unordered_mapint,int map;//总组合数目int count0;for(int i0;iA.size();i){for(int j0;jB.size();j){map[A[i]B[j]];}}for(int i0;iC.size();i){for(int j0;jD.size();j){int iter0-(C[i]D[j]);//如果能找到if(map.find(iter) !map.end()){countmap[iter];}}}return count;}
};
