LeetCode 454.四数相加 II

这篇具有很好参考价值的文章主要介绍了LeetCode 454.四数相加 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

454.四数相加 II

一、题目

给你四个整数数组 nums1nums2nums3nums4 ,数组长度都是 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. 初始化一个哈希表 sumAB,用于记录数组 nums1nums2 中元素的和及其出现的次数。
  2. 遍历数组 nums1nums2 的所有元素组合,并将元素和及其出现次数存储在 sumAB 中。
  3. 初始化一个变量 count,用于记录满足条件的四元组的个数,初始值为 0。
  4. 遍历数组 nums3 和 nums4的所有元素组合:
    • 计算当前两个元素的和 target
    • sumAB 中查找是否存在和为 target 的相反数。
    • 如果存在相反数,将对应的出现次数累加到 count 中。
  5. 返回 count 作为最终的结果。
详细实现
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int count = 0;
        unordered_map<int, int> sumAB; // 记录 nums1 和 nums2 的元素和及其出现次数
        
        // 遍历 nums1 和 nums2,记录元素和及其出现次数
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                sumAB[num1 + num2]++;
            }
        }
        
        // 遍历 nums3 和 nums4,查找目标和的相反数,并累加对应的次数到结果中
        for (int num3 : nums3) {
            for (int num4 : nums4) {
                int target = -(num3 + num4);
                if (sumAB.find(target) != sumAB.end()) {
                    count += sumAB[target];
                }
            }
        }
        
        return count;
    }
};
算法分析
  • 时间复杂度:算法的时间复杂度为 O(n^2),其中 n 是数组的长度。遍历数组 nums1nums2 的时间复杂度为 O(n^2),遍历数组 nums3nums4 的时间复杂度也为 O(n^2),因此总的时间复杂度为 O(n^2)。
  • 空间复杂度:算法使用了一个哈希表 sumAB 来存储元素和及其出现次数,哈希表的大小最多为数组 nums1nums2 的组合数,即 O(n^2)。因此,算法的空间复杂度为 O(n^2)。
方法二:两个哈希表(方法一的复杂版,不推荐)

这是一个不好的办法,超出了时间限制,各位看官看看即可……文章来源地址https://www.toymoban.com/news/detail-523467.html

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int n = nums1.size();
        int count = 0;
        //创建两个哈希表,key值为两个数组元素的和,value值为组成这个和的两个下标
        multimap<int,multimap<int,int>> numA;
        multimap<int,multimap<int,int>> numB;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n;j++){
                numA.insert(make_pair(nums1[i] + nums2[j], multimap<int, int>{{i, j}}));
            }
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n;j++){
                numB.insert(make_pair(nums3[i] + nums4[j], multimap<int, int>{{i, j}}));
            }
        }
        //遍历numA寻找numB中对应元素
        for(auto iterA = numA.begin();iterA != numA.end();iterA++){
            for(auto iterB = numB.begin();iterB != numB.end();iterB++){
                if(iterA->first + iterB->first == 0){
                    count++;
                }
            }
        }
        return count;
    }
};

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【力扣】454. 四数相加 II

    【力扣】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 解释: 两个元组如下

    2024年02月16日
    浏览(39)
  • 【代码随想录06】454. 四数相加 II 383. 赎金信 15. 三数之和 18. 四数之和

    题目描述 给你四个整数数组 nums1 、 nums2 、 nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足: 0 = i, j, k, l n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 做题思路 本题可以使用哈希表, key 为 nums1[i] + nums2[j] 的和, value 为其出现的次数。然后再遍历 nums3 和

    2024年01月16日
    浏览(44)
  • LeetCode454. 4Sum II

    Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that: 0 = i, j, k, l n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 Example 1: Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2] Output: 2 Explanation: The two tuples are: (0, 0, 0, 1) - nums1[0] + nums2[0] + nums3[0] +

    2024年02月06日
    浏览(39)
  • leetcode刷题(字符串相加、包含每个查询的最小区间、模拟行走机器人、环形子数组的最大和、满足不等式的最大值、四数之和、树中距离之和)

    目录 1、字符串相加 2、包含每个查询的最小区间 3、模拟行走机器人 4、环形子数组的最大和 5、满足不等式的最大值 6、四数之和 7、 树中距离之和

    2024年02月10日
    浏览(45)
  • 代码随想录-哈希表02 第454题.四数相加II&383. 赎金信&第15题. 三数之和&第18题. 四数之和

    第454题.四数相加II 第454题.四数相加II 条件:四个数组中分别取一个,相加和为0,求满足条件的元组个数 思路使用1个map,mapA保存 s1 s2中相加和及其出现次数 遍历s3 s4,去判断是否满足 0 - (s3[i] + s4[j]) 在mapA中,并统计出现次数 383. 赎金信 383. 赎金信 题目要求,s1 是否能由s

    2024年02月12日
    浏览(41)
  • LeetCode_Day6 | 四数相加||、赎金信、三数之和、四数之和!

    详情leetcode链接 解题步骤: 首先定义 map,key放a和b两数之和,value 放a和b两数之和出现的次数。 遍历大A和大B数组,统计两个数组元素之和,和出现的次数,放到map中。 定义int变量count,用来统计 a+b+c+d = 0 出现的次数。 在遍历大C和大D数组,找到如果 0-(c+d) 在map中出现过的话

    2024年02月09日
    浏览(41)
  • 我在代码随想录|写代码Day7之454.四数相加II ,​ 383. 赎金信​,​ 15. 三数之和​

    题目  解题思路 四个数字相加的和为0,我们要选俩数组,让他们的笛卡尔积储存在哈希表中,然后我们要找的是这俩数和的相反数,然后就是将后面俩数组相加在后面的数组和中找相反数.   解题思路 题目意思是让在字符串1中找到字母组成字符串2所以找字符串1的数量.所以可以用

    2024年01月20日
    浏览(39)
  • 【刷题】 leetcode 2 .两数相加

    我们来看看题目,,,, 往往困难的题只需要 简单的叙述 。 好像只用找到两个数,整合成一个链表就可以。应该 首先 我最快想到思路是 分别根据两个链表求出对应数 然后加一起 ,得到和 再把和拆分储存到链表里 为此我们需要手撕一下链表头插。 一顿操作猛如虎,一看

    2024年01月19日
    浏览(45)
  • leetcode 445. Add Two Numbers II(两数相加)

    用链表代表2个数字,这2个数字相加的和用链表返回。 最高位在链表的head. 思路: 1.链表逆序 数字相加是从低位到高位的,然而链表中的数字是从高位指向低位。 所以涉及到链表的逆序。 逆序之后只需从head到tail把两个链表的数字相加,再用一个int表示进位。 链表的逆序

    2024年02月16日
    浏览(43)
  • LeetCode刷题:142. 环形链表 II

    题目: 是否独立解决: 否,参考了解题思路解决问题,思考了用快慢指针,栈,统计链表数量定位尾巴节点(因为是环形链表所以是死循环,链表数量用while循环统计不出来)都没解决 解题思路:这题其实和环形链表一样的解题思路,用哈希set将数据都存储进去,如果发现

    2024年01月21日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包