网站推广服务属于广告吗,推盟,青岛知名网站建设多少钱,怎么建立手机网站原题链接#xff1a;力扣454.四数相加
根据题意就是需要计算 nums1[i] nums2[j] nums3[k] nums4[l] 0 暴力解法就直接4个for循环逐个遍历相加看看是否等于0即可 时间复杂度为O(n^4)
因为怎么样都要进行容器遍历#xff0c;所以4个数组优解应为O(n^2) 为什么是O(n^2)? …原题链接力扣454.四数相加
根据题意就是需要计算 nums1[i] nums2[j] nums3[k] nums4[l] 0 暴力解法就直接4个for循环逐个遍历相加看看是否等于0即可 时间复杂度为O(n^4)
因为怎么样都要进行容器遍历所以4个数组优解应为O(n^2) 为什么是O(n^2)?
map 存一个数组如 A。然后计算三个数组之和如 BCD。时间复杂度为O(n)O(n^3)得到 O(n^3). map 存三个数组之和如 ABC。然后计算一个数组如 D。时间复杂度为O(n^3)O(n)得到 O(n^3). map 存两个数组之和如AB。然后计算两个数组之和如 CD。时间复杂度为O(n2)O(n2)得到 O(n^2).
所以只需要遍历前俩个数组每个元素的和存储到map1中将出现的次数存储到map1的值中。 再遍历后两个数组每个元素的和用0 减去这个和 的值(反推得到map1某个元素的值 这个和等于0)到map1里面去找如果有则代表map1的值 这个和等于0. 那么count就等于count 上这个map1target
全代码
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {unordered_mapint,int map1;int count 0;for(int i : nums1){for(int j : nums2){map1[ij];}}for(int i : nums3){for(int j : nums4){int target 0 - (ij);if(map1.find(target) ! map1.end() ){count map1[target];}}}return count;}
};
