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

我会带着你远行 2022-12-24 06:00 82阅读 0赞

> **LeetCode题号：**[454. 四数相加 II][454. _ II]
> 
> 描述：给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A\[i\] + B\[j\] + C\[k\] + D\[l\] = 0。
> 
> **例如:**
> 
> 输入:  
> 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

> **思路：**
> 
>         先定义一个map，key存放任意两组数组各两数之和，value存两数之和出现的次数；再遍历剩下两组，判断map中是否存在key（这里需要注意以下，取c+d之和的相反数去判断该key是否存在于map中），存在即returnCount 加该key的次数 ；详情看代码！如下

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70][]

class Solution {
        public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
            int count = 0;
            //计算出所有a+b之和的情况，value存出现次数
            HashMap<Integer, Integer> map_ab = new HashMap<Integer, Integer>(16);
            for (int a : A) {
                for (int b : B) {
                    int value_ab = a + b;
                    //判断key是否存在
                    boolean ok = map_ab.containsKey(value_ab);
                    if (!ok) {
                        map_ab.put(value_ab, 1);
                    } else {
                        //存在key，次数加一
                        map_ab.put(value_ab, map_ab.get(value_ab) + 1);
                    }
                }
            }
            //遍历cd取c+d
            for (int c : C) {
                for (int d : D) {
                    int value_cd = c + d;
                    //先判断是否存在key；要求相加为零，特地key取反；若存在，则满足a+b+c+d = 0;
                    boolean ok = map_ab.containsKey(-value_cd);
                    //不存在，直接跳出此次循环
                    if (!ok) {
                        continue;
                    }
                    //key对应的value
                    int mu = map_ab.get(-value_cd);
                    count += mu;
                }
            }
            return count;
        }
    }

--------------------

**往期回顾：**

【1】[LeetCode-164. 最大间距(Java实现)][LeetCode-164. _Java]

【2】[LeetCode-1370. 上升下降字符串(Java实现)][LeetCode-1370. _Java]

--------------------

> ❤如果文章对您有所帮助，就在文章的右上角或者文章的末尾点个赞吧！(づ￣ 3￣)づ 
> 
> ❤如果喜欢大白兔分享的文章，就给大白兔点个关注吧！(๑′ᴗ‵๑)づ╭❤～
> 
> ❤对文章有任何问题欢迎小伙伴们下方留言或者入群探讨【群号：708072830】
> 
> ❤鉴于个人经验有限，所有观点及技术研点，如有异议，请直接回复讨论(请勿发表攻击言论)

[454. _ II]: https://leetcode-cn.com/problems/4sum-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk3MDc0Mw_size_16_color_FFFFFF_t_70]: /images/20221120/a51c1abae6a7443f88101d141b7090c7.png
[LeetCode-164. _Java]: https://blog.csdn.net/weixin_43970743/article/details/110192475
[LeetCode-1370. _Java]: https://blog.csdn.net/weixin_43970743/article/details/110189600