526互联

LeetCode 454.四数相加 II

发布时间 2023-10-23 22:12:43作者: 白布鸽

题目描述

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

描述

image

第一次提交的代码

import java.util.Map;
import java.util.HashMap;
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //四数相加退化成两数之和，但是时复会变为O(n^2)
        int lenOfMul=nums1.length*nums1.length;

        int count=0;
        int minus=0;
        Map<Integer,Integer> map = new HashMap<>();

        for(int i=0;i<nums1.length;i++){
           for(int j=0;j<nums1.length;j++){
               int temp=nums1[i]+nums2[j];
               if(map.containsKey(temp)){
                   map.put(temp,map.get(temp)+1);
               }else{
                   map.put(temp,1);
               }
           }
        }

        for(int i=0;i<nums1.length;i++){
            for(int j=0;j<nums1.length;j++){
                minus=(0-(nums3[i]+nums4[j]));
                if(map.containsKey(minus)){
                    count+=map.get(minus);
                }
            }
        }

        return count;
    }
}

结果图：
image

思路：
四数相加退化成两数之和，但是O(n)会变成O(n^2)，没办法，给的数组有四个，这个时间复杂度相对还正常的- -，也不能说退化成两数之和吧，毕竟两数之和的代码逻辑搞不好的话执行时间就差的比较多了。
因为这个题目并不需要返回元组索引，所以在遍历前两个数组的时候，用HashMap来存储各个索引相加的值(键)，索引值相加结果出现的次数作为值，这样在遍历后两个数组的时候，就可以知道当前两个索引相加结果在之前两个数组出现的次数，变相的实现了(i, j, k, l)。

学习到的东西

我Java基础还是菜，map.getOrDefault(key,initVal)这个方法居然都没想起来，菜狗啊...
用了map的这个方法，执行速度快了不少。

更新的代码如下：

import java.util.Map;
import java.util.HashMap;
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //四数之和退化成两数之和，但是时复会变为O(n^2)
        int lenOfMul=nums1.length*nums1.length;

        int count=0;
        int minus=0;
        Map<Integer,Integer> map = new HashMap<>();

        for(int i=0;i<nums1.length;i++){
           for(int j=0;j<nums1.length;j++){
               int temp=nums1[i]+nums2[j];
               map.put(temp,map.getOrDefault(temp,0)+1);
           }
        }

        for(int i=0;i<nums1.length;i++){
            for(int j=0;j<nums1.length;j++){
                minus=(0-(nums3[i]+nums4[j]));
                count+=map.getOrDefault(minus,0);
            }
        }

        return count;
    }
}

执行效果如下图：
image