网站打开速度规定多长时间,全国最大机械采购平台,如何用网站做淘宝客,深圳网站制作建站每日一题(LeetCode)----哈希表–四数相加 II
1.题目#xff08;454. 四数相加 II#xff09;
给你四个整数数组 nums1、nums2、nums3 和 nums4 #xff0c;数组长度都是 n #xff0c;请你计算有多少个元组 (i, j, k, l) 能满足#xff1a;
0 i, j, k, l nnu…每日一题(LeetCode)----哈希表–四数相加 II
1.题目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
解释
两个元组如下
1. (0, 0, 0, 1) - nums1[0] nums2[0] nums3[0] nums4[1] 1 (-2) (-1) 2 0
2. (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
2.解题思路
思路一分组哈希法
1.一共有四组整数数组我们每两个为一组这里我们以前两组整数数组为一组后两组整数数组为一组
2.创建两个哈希表这里用unordered_map两个哈希表的键值都是其组内第一个整数数组中的元素和第二个整数数组中的元素相加所得的数实值是当前键值的数出现的次数
3.进行遍历每组中的第一个整数数组的每个数都和第二个整数数组相加一遍得到的数存入对应的哈希表中
4.定义一个结果变量遍历其中一个哈希表每遍历到哈希表中一个元素我们取出这个哈希表中的实值然后以0减去当前哈希表中的键值所得到的数作为另一个哈希表中的键值取出另一个的实值取出的这两个实值进行相乘然后加到我们的结果变量上即可
3.写出代码
思路一的代码
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {int lengthnums1.size();unordered_mapint,int ma1;unordered_mapint,int ma2;for(int i0;ilength;i){for(int j0;jlength;j){if(ma1.count(nums1[i]nums2[j])0){ma1[nums1[i]nums2[j]]1;}else{ma1[nums1[i]nums2[j]];}if(ma2.count(nums3[i]nums4[j])0){ma2[nums3[i]nums4[j]]1;}else{ma2[nums3[i]nums4[j]];}}}int res0;for(auto v:ma1){if(ma2.count(0-v.first)!0){resv.second*ma2[0-v.first];}}return res;}
};
