php能做手机网站吗,做百度网站排,关键字排名查询,蚌埠做网站哪家好题目链接
题目描述
给你四个整数数组 nums1、nums2、nums3 和 nums4 #xff0c;数组长度都是 n #xff0c;请你计算有多少个元组 (i, j, k, l) 能满足#xff1a;
0 i, j, k, l n nums1[i] nums2[j] nums3[k] nums4[l] 0
示例 1#xff1a;
输入…题目链接
题目描述
给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足
0 i, j, k, l n nums1[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 题解
审题
这道题要注意审题结果是不去重的即使两种情况都是4个0相加只要下标的排列顺序不同就是不同的结果
思路
这道题有些类似于day1做的两数之和相加(day1 两数之和相加)当时就用到了哈希表 在遍历数组的同时 去查找哈希表中是否存在符合要求的数 这道题只是变成了四个数组相加 实际上 我们可以两两分组 分别计算两个数组中两数相加的情况 比如nums1和nums2中两数相加出现了-5这种情况我们就去找nums3和nums4相加有没有出现5的情况 那应该使用哪种哈希表呢是数组set还是map? 题目中的数字可以变得很大如果用数组可能存在元素过少而下标过大的情况下标要作为映射 如果用set也不行。比如nums1{-2,-3}nums2{-2,-3}中两数相加出现了-5 可能存在两种情况[0,1]和[1,0] set只能说明存在-5这种情况但是不能反映出有几种排列。 所以要用map 思路如图所示 让两数相加的结果作为Key,排列组合产生的方式数作为Vaue
代码书写
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {unordered_mapint,intmap;int result0;//遍历两个数组统计两两数之和for(int i0;inums1.size();i){for(int j0;jnums2.size();j){map[nums1[i]nums2[j]];}}for(int i0;inums3.size();i){for(int j0;jnums4.size();j){//比如说剩下两个数组的某两个元素之和为5则在map中找有没有和为-5的if(map.find(-nums3[i]-nums4[j])!map.end()){ //如果有resultmap[-nums3[i]-nums4[j]]; }}}return result;}
};
