网站设计公司排名知乎,手机门户WordPress主题,做网站起什么名字比较好,莆田seo代码随想录二刷 #xff5c; 哈希表 #xff5c;四数相加II 题目描述解题思路 代码实现 题目描述
454.四数相加II
给你四个整数数组 nums1、nums2、nums3 和 nums4 #xff0c;数组长度都是 n #xff0c;请你计算有多少个元组 (i, j, k, l) 能满足#xff1a;
0… 代码随想录二刷 哈希表 四数相加II 题目描述解题思路 代码实现 题目描述
454.四数相加II
给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足
0 i, j, k, l nnums1[i] nums2[j] nums3[k] nums4[l] 0
示例 1
输入nums1 [1,2], nums2 [-2,-1], nums3 [-1,2], nums4 [0,2] 输出2 解释 两个元组如下
(0, 0, 0, 1) - nums1[0] nums2[0] nums3[0] nums4[1] 1 (-2) (-1) 2 0(1, 1, 0, 0) - nums1[1] nums2[1] nums3[0] nums4[0] 2 (-1) (-1) 0 0
示例 2
输入nums1 [0], nums2 [0], nums3 [0], nums4 [0] 输出1
提示
n nums1.lengthn nums2.lengthn nums3.lengthn nums4.length1 n 200-228 nums1[i], nums2[i], nums3[i], nums4[i] 228
解题思路 代码实现
这道题目是四个独立的数组只要找到A[i] B[j] C[k] D[l] 0就可以不用考虑有重复的四个元素相加等于0的情况。
本题解题步骤
首先定义 一个unordered_mapkey放a和b两数之和value 放a和b两数之和出现的次数。遍历大A和大B数组统计两个数组元素之和和出现的次数放到map中。定义int变量count用来统计 abcd 0 出现的次数。在遍历大C和大D数组找到如果 0-(cd) 在map中出现过的话就用count把map中key对应的value也就是出现次数统计出来最后返回统计值 count
class Solution {
public:int fourSumCount(vectorint A, vectorint B, vectorint C, vectorint D) {unordered_mapint, int umap;for (int a : A) {for (int b : B) {umap[a b];}}int count 0;for (int c : C) {for (int d : D) {if (umap.find(0 - (c d)) ! umap.end()) {count umap[0 - (c d)];}}}return count;}
};时间复杂度O(n^2) 空间复杂度O(n^2)最坏情况下A和B的值各不相同相加产生的数字个数为n ^ 2
