力扣第454题 四数相加 || c++哈希map使用

题目

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

思路和解题方法

1. 首先，代码创建了一个无序映射（unordered_map）ans_map，用于存储和以及对应出现次数的键值对。
2. 然后，通过两层嵌套的循环遍历nums1和nums2中的元素，将它们的和作为键，在ans_map中对应的值加1。
3. 接下来，定义一个计数器变量count，用于统计和为零的四元组的数量。
4. 再次通过两层嵌套的循环遍历nums3和nums4中的元素，对于每对元素，计算它们的和，并在ans_map中查找是否存在等于该和取负的键。
5. 如果存在，说明存在一组与当前元素配对后和为零的四元组，将ans_map中对应键的值累加到count中。
6. 最后，返回count作为结果，即和为零的四元组的数量。

复杂度

        时间复杂度:

                O(n^2)

首先，通过两层嵌套的循环遍历nums1和nums2，计算并存储了所有可能的两个元素的和，时间复杂度为O(N^2)。

然后，再通过两层嵌套的循环遍历nums3和nums4，对于每对元素，需要在ans_map中查找是否存在等于该和取负的键，时间复杂度为O(N^2)。

        空间复杂度

                O(n^2)

空间复杂度，代码使用了一个额外的无序映射ans_map来存储和以及对应出现次数的键值对。映射的大小取决于nums1和nums2中元素的组合情况，最坏情况下可能达到O(N^2)。因此，代码的空间复杂度为O(N^2)。

c++ 代码

 ​

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> ans_map; // 创建存储和及其出现次数的无序映射
        
        // 计算 nums1 和 nums2 中元素的和，并将和作为键，出现次数作为值存入无序映射中
        for(int i:nums1)
            for(int j:nums2)
            {
                ans_map[i+j]++;
            }
 
        int count = 0; // 存储和为零的四元组数量
        
        // 遍历 nums3 和 nums4 中元素的组合，并检查是否存在和为零的对应四元组
        for(int i:nums3)
            for(int j:nums4)
            {
                if(ans_map.find(0-(i+j))!=ans_map.end()) // 如果存在和为零的对应四元组
                {   
                    count +=  ans_map[0-(i+j)]; // 更新计数器
                }
            }
        
        return count; // 返回和为零的四元组数量
    }
};

相关知识

1. 无序映射（unordered_map）：无序映射是一种关联容器，它提供了快速的键-值查找。在这段代码中，使用无序映射ans_map来存储和以及对应出现次数的键值对。通过键可以快速查找对应的值，并在O(1)的时间复杂度内完成查找操作。

2. 嵌套循环：这段代码使用了两层嵌套的循环来遍历数组。第一层循环遍历nums1数组的元素，第二层循环遍历nums2数组的元素。后面同样的方式遍历nums3和nums4数组。嵌套循环常用于需要对多维数据进行全排列或组合的情况。

3. 查找和计数：代码中使用了无序映射来进行查找和计数操作。在第一个嵌套循环中，将两个数组元素的和作为键，通过增加对应键的值来计数和的出现次数。在第二个嵌套循环中，通过判断和的取负是否存在于ans_map中来确定是否存在和为零的四元组，并将对应键的值累加到计数器变量count中。

4. 数组遍历和元素访问：代码中通过使用范围for循环来遍历数组的元素。通过迭代器或下标访问方式，可以获取数组中的每个元素进行进一步的操作。

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。