四数相加

Leetcode 11.27打个卡（https://github.com/ydSerendipity/Leetcode/blob/master/code/fourNumSumZero.java） 

给定四个包含整数的数组列表 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 。（来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/4sum-ii）

 拿着题目第一想法直接四个for循环，然后判断，最后返回计数的就可以了，果不其然爆了，就知道没这么简单让我过。没有大佬们那么熟悉直接用哈希，第二次上的是ArrayList，最后还是有个套了3个for循环，提交还是爆了。看了提示说要用哈希，然后恶补了一下哈希：(使用getOrDefault(key, default)时间和空间消耗都要少)

package Leetcode;

import java.util.ArrayList;
import java.util.HashMap;

public class fourNumSumZero {

    public static void main(String[] args){

        fourNumSumZero obj = new fourNumSumZero();
        int[] A = {-1, -1};
        int[] B = {-1, 1};
        int[] C = {-1, 1};
        int[] D = {1, -1};
        System.out.println(obj.fourSumCount(A, B, C, D));
    }

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

        int len = A.length;
        int count = 0;
//        ArrayList<Integer> l = new ArrayList<Integer>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0;i < len;i++){
            for (int j = 0;j < len;j++){
                int sum = A[i]+B[j];
//                if(map.containsKey(sum)){
//                    map.put(sum, map.get(sum)+1);
//                }else {
//                    map.put(sum, 1);
//                }
//                getOrDefault(key, default)是查询有这个key则返回相应的value，没有则返回default值
//                最开始没有，返回default为0，最后加一，这个过程就是在计数的过程
                map.put(sum, map.getOrDefault(sum, 0)+1);
            }
        }
        for (int k = 0;k < len;k++){
            for (int l = 0;l < len;l++){
                int r = C[k] + D[l];
                if(map.containsKey(-r)){
                    count += map.get(-r);
                }
            }
        }
        return count;
    }
}

 

本文地址：https://blog.csdn.net/ydydyd00/article/details/110232392