[LeetCode] day19 454. 四数相加 II

题目链接

题目描述

给你四个整数数组 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
解释：
两个元组如下：

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

题解

审题

这道题要注意审题，结果是不去重的，即使两种情况都是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(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int>map;
        int result=0;
        //遍历两个数组，统计两两数之和
       for(int i=0;i<nums1.size();i++){
        for(int j=0;j<nums2.size();j++){
           map[nums1[i]+nums2[j]]++;
        }
       }
       for(int i=0;i<nums3.size();i++){
        for(int j=0;j<nums4.size();j++){
            //比如说剩下两个数组的某两个元素之和为5，则在map中找有没有和为-5的
            if(map.find(-nums3[i]-nums4[j])!=map.end()){ //如果有
             result+=map[-nums3[i]-nums4[j]]; 
            }
        }
       }
       return result;
    }
};