Leetcode刷题java之454. 四数相加 II（一天一道编程题之五十一天）

我不是女神ヾ 2023-07-22 15:26 34阅读 0赞

执行结果：

通过

显示详情

执行用时 :76 ms, 在所有 Java 提交中击败了93.35% 的用户

内存消耗 :58.8 MB, 在所有 Java 提交中击败了26.13%的用户

题目：

给定四个包含整数的数组列表 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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/4sum-ii  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

将四个拆分成两个，用两个来构建字典，用另外两个来查找相反数。

代码：

class Solution {
        public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
            HashMap<Integer,Integer> map=new HashMap<>();
            int result=0;
            for(int i=0;i<A.length;i++)
            {
                for(int j=0;j<B.length;j++)
                {
                    map.put(A[i]+B[j],map.getOrDefault(A[i]+B[j],0)+1);
                }
            }
            for(int i=0;i<C.length;i++)
            {
                for(int j=0;j<C.length;j++)
                {
                    result+=map.getOrDefault(-C[i]-D[j],0);
                }
            }
            return result;
        }
    }