LeetCode 454.四数相加 II（C++）

系统管理员 2021-12-16 17:47 158阅读 0赞

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 `(i, j, k, l)` ，使得 `A[i] + B[j] + C[k] + D[l] = 0`。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

例如:

输入:
    A = [ 1, 2]
    B = [-2,-1]
    C = [-1, 2]
    D = [ 0, 2]
    
    输出:
    2
    
    解释:
    两个元组如下:
    1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
    2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

#include <iostream>
    #include <unordered_map>
    #include <vector>
    
    int fourSumCount(vector<int> &A, vector<int> &B, vector<int> &C, vector<int> &D){
        unordered_map<int, int> store;
        for(auto &i : A)//使用map容器作为查找容器（如果四数之和为0，任意两数之和与另外两数之和，互为相反数） 
            for(auto &j : B)
                ++store[i+j];
        int results = 0;
        for(auto &m : C)
            for(auto &n : D)
                if(store.count(-m-n))//查找我们需要的两数之和，在map容器中是否存在 
                    results += store[-m-n];//因为产生这一和的两个数可能不止一组 
        return results;
    }
    
    int main()
    {
        vector<int> A = { 1, 2 };
        vector<int> B = { -2, -1 };
        vector<int> C = { -1, 2 };
        vector<int> D = { 0, 2 };
        cout << fourSumCount(A, B, C, D) << endl;
        
        return 0;
    }

转载于:https://www.cnblogs.com/Mayfly-nymph/p/10549289.html

发表评论取消回复

表情：

评论列表（有 0 条评论，158人围观）

还没有评论，来说两句吧...

相关阅读

相关 Leetcode刷题day7|454.四数相加II, 383. 赎金信,15. 三数之和 ,18四数之和

文章目录一、四数相加II 思路注意 AC代码二、赎金信

旧城等待，/ 2024年03月31日 05:04/ 0 赞/ 23 阅读

相关 LeetCode-454. 四数相加 II

目录题目思路暴力法哈希表题目来源 [454. 四数相加 II][454. _ II] 题目思路有三种情况可

た入场券/ 2024年03月24日 15:25/ 0 赞/ 20 阅读

相关第454题.四数相加II

第454题.四数相加II 题干背景重要思路参考代码题干背景给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (

谁借莪１个温暖的怀抱￠/ 2024年03月17日 21:57/ 0 赞/ 22 阅读

相关 LeetCode-454. 四数相加 II(Java实现)

> LeetCode题号：[454. 四数相加 II][454. _ II] > > 描述：给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i,

我会带着你远行/ 2022年12月24日 06:00/ 0 赞/ 83 阅读

相关 leetcode 454 四数相加II

前言题目：[454. 四数相加 II][454. _ II] 参考答案：[454. 四数相加 II-力扣官方题解][454. _ II-] ------------

布满荆棘的人生/ 2022年09月09日 04:58/ 0 赞/ 112 阅读

相关力扣-454题四数相加II（C++）- map

题目链接：[https://leetcode-cn.com/problems/4sum-ii/][https_leetcode-cn.com_problems_4sum-ii]

素颜马尾好姑娘i/ 2022年09月08日 10:26/ 0 赞/ 178 阅读

相关 Leetcode 454. 四数相加 II（DAY 151） ---- LeetCode 精选 TOP 面试题

文章目录原题题目代码实现（首刷未优化版 C++）代码实现（首刷优化版） -------------------- 原题

今天药忘吃喽~/ 2022年09月07日 09:49/ 0 赞/ 103 阅读

相关 leetcode 454. 4Sum II | 454. 四数相加 II（Java）

题目 [https://leetcode.com/problems/4sum-ii/][https_leetcode.com_problems_4sum-ii] ![

小灰灰/ 2022年09月06日 04:58/ 0 赞/ 102 阅读

相关 LeetCode：四数相加（四个数组）、四数之和（一个数组）

public class Solution_454 { / 四数相加：给定四个包含整数的数组列表 A , B

爱被打了一巴掌/ 2021年12月20日 10:49/ 0 赞/ 169 阅读

相关 LeetCode 454.四数相加 II（C++）

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 `(i, j, k, l)` ，使得 `A[i] + B[j] + C[k] + D[l] = 0`

系统管理员/ 2021年12月16日 17:47/ 0 赞/ 159 阅读