454. 四数相加 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了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

提示：

n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/4sum-ii

暴力法自然就是4重for循环（不过这题用暴力是超时的）

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int count=0;
        for(int a:nums1)
        {
            for(int b:nums2)
            {
                for(int c:nums3)
                {
                    for(int d:nums4)
                    {
                        if(a+b+c+d==0)
                        count++;
                    }
                }
            }
        }
        return count;
    }
};

可以用哈希法来优化，创建一个unordered_map,遍历nums1和nums2来将所有a+b的值存入map中，key值是a+b的值，value是a+b的出现的次数（unordered_map中key值是不能重复的，所以value值只有0和1）。再遍历nums3和nums4来找到map里等于0-（c+d）的key值，记录到count里。把原来的四重for循环,拆成了两个二重for循环，第一个二重for循环存数据，制造一个哈希表,第二个for循环在这个哈希表里查相符合的数据。

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int count=0;
        unordered_map<int,int> umap;
        for(int a:nums1)
        {
            for(int b:nums2)
            {
                umap[a+b]++;
            }
        }
        for(int c:nums3)
        {
            for(int d:nums4)
            {
                if(umap.find(0-(c+d))!=umap.end())
                    count+=umap[0-(c+d)];
            }
        }
        return count;
    }
};

关于hash表的题目中map和set的选用：map拥有key值和value值，可以存放一个元素两个维度的数据这题就是a+b的值和出现的次数。而set只能存放有没有出现a+b的值。文章来源地址https://www.toymoban.com/news/detail-576052.html

到了这里，关于454. 四数相加 II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！