Leetcode 454： 4Sum II

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

说人话：

给定四个包含整数的数组列表 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 。所有整数的范围在 -2²⁸ 到 2²⁸ - 1 之间，最终结果不会超过 2³¹ - 1 。

几个要点：

• N 不会超过 500
• 最终结果不会超过 2³¹-1，确保了不会发生溢出
• 题目要求的是多少个元组，只需要回答个数

[法1] 暴力法

思路

最简单的方法肯定是进行四层 for 循环，找到满足条件的元组就累计加1。

代码

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {

        int result = 0;

        for(int a=0;a<A.length;a++){
            for(int b=0;b<B.length;b++){
                for(int c=0;c<C.length;c++){
                    for(int d=0;d<D.length;d++){
                        if(A[a]+B[b]+C[c]+D[d] == 0){
                            result ++;
                        }
                    }
                }
            }
        }
        return result;
    }
}

提交结果

代码分析

• 时间复杂度：很显然四层 for 循环是 O(n⁴)
• 空间复杂度：O(1)

改进思路

肯定是不能用四层 for 循环的，哪怕 N 不会超过 500，n⁴ 也是一个非常大的数字了。

一个思路就将 A[a] 的结果存到集合中，这样我们就只需要找 B[b] + C[c] + D[d] = target -A[a] 的元组了，这样就优化到了 O(n³)。

再进一步，因为 N 最大只是 500， N² 也才 250000，所以我们可以将 A[i] + B[i] 的结果存到集合中，然后就只需要找 C[c] + D[d] = target - A[a] - B[b] 的元组了。O(n²）= 250000 的时间复杂度我们还是可以接受的。

[法2] 利用查找集

思路

• 将 A[a] + B[b] 的结果存到集合中
  • 这里是要选择哪种集合呢？ Set 还是 Map 呢？
  • 因为 A[a] + B[b] 的结果可能是重复的，所以我们需要记录这个结果出现的次数，所以需要用 Map。
• 找 C[c] + D[d] = target - A[a] - B[b] 的元组

代码

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {

        int result = 0;

        Map<Integer,Integer> map = new HashMap<>();

        //存入 A[a] + B[b] 的所有情况及其出现的次数
        for(int a=0;a<A.length;a++){
            for(int b=0;b<B.length;b++){
                int temp = A[a] + B[b];
                Integer value = map.get(temp);
                if(value != null && value>0){
                  	//记录次数
                    value++;
                    map.put(temp,value);
                }else{
                    map.put(temp,1);
                }
            }
        }

        //寻找 C[c] + D[d] = target - A[a] - B[b]
        for(int c=0;c<C.length;c++){
            for(int d=0;d<D.length;d++){
                Integer value = map.get(0-C[c]-D[d]);
                if(value!=null && value>0){
                  	//累计次数
                    result += value;
                }
            }
        }
        return result;
    }
}

代码分析

• 时间复杂度：O(n²)
• 空间复杂度：O(n²)