欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

四数相加

程序员文章站 2022-03-19 16:19:51
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 ......

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

相关标签: Leetcode java