当前位置：首页 > news >正文

Leetcode刷题由浅入深之哈希法——454. 四数相加Ⅱ

news 2025/4/27 5:57:37

（一）四数相加的C++实现

写法一（哈希映射）

简化版：

（二）复杂度分析

时间复杂度

空间复杂度

（三）总结

【题目链接】454. 四数相加Ⅱ - 力扣（LeetCode）

给你四个整数数组 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

（一）四数相加的C++实现

写法一（哈希映射）

解题思路：

上一篇写过两数相加（Leetcode刷题由浅入深之哈希法——1. 两数之和-CSDN博客）的算法，我们是将遍历过的数字存储在映射中，key为元素的值，value为数字在数组中对应的索引，循环过程中，使用target减去其中一个数字，去找另一个符合要求的数字。此题，我们也可以采用类似的方法。

此题是从四个数组中分别选一个数字，要求四个数字之和为target。为了节省时间，我们将前两个数组的所有组合之和，以及对应的索引存储在nums_map1中；利用后两个数组的所有组合之和计算出符合要求的前两个数字之和，并在nums_map1中寻找。

本题目只需要计数，而不需要返回每一种解的下标，因此直接设置一个计数变量count，若在nums_map1中找到加1即可。

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, vector<vector<int>>> nums_map1;for(int i=0; i < nums1.size(); i++){for(int j=0; j < nums2.size(); j++){nums_map1[nums1[i] + nums2[j]].push_back({i,j});}}int count = 0;for(int i=0; i < nums3.size(); i++){for(int j=0; j < nums4.size(); j++){int temp = - nums3[i] - nums4[j];if(nums_map1.find(temp) != nums_map1.end())count += nums_map1.find(temp)->second.size();}}return count;}
};

简化版：

本题目只要求输出一共有几种解法，因此，在定义nums_map1时，value直接定义为整型即可，计算出符合要求的解法直接+1计数即可。

在遍历过程中，数组中的元素需要参与计算，因此可以直接使用auto遍历元素。

改进以上两点，更简明的代码如下：

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> nums_map1;for(auto i : nums1){for(auto j : nums2)nums_map1[i + j]++;}int count = 0;for(auto i : nums3){for(auto j : nums4)count += nums_map1[-(i + j)];}return count;}
};

（二）复杂度分析

时间复杂度

双重循环，整个函数的时间复杂度为 $O(n_1n_2+n_3n_4)$ 。通常情况下，如果四个数组的长度都为 n，那么时间复杂度可以简化为 $O(n^2)$ 。

空间复杂度

哈希表占用的空间：使用 unordered_map 来存储 nums1 和 nums2 中元素两两相加的结果及其出现的次数。在最坏的情况下，nums1 和 nums2 中元素两两相加的结果都不相同，哈希表中需要存储 n1∗n2 个键值对。因此，哈希表所占用的空间复杂度为 $O(n_1n_2)$ 。