【LeetCode】454. 四数相加 II-拓冰建站

今日学习的文章链接和视频链接

leetcode题目地址：454. 四数相加 II

代码随想录题解地址：代码随想录

题目简介

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

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

看到题目的第一想法(可以贴代码）

1. 暴力解法：把四个数组分成两个一组，共两组，求出他们每个元素排列组合的和，形成两个List(或者说ArrayList)，此处不用Set是因为，要容许重复的元素存在。//超出时间限制

// 超出时间限制
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {List<Integer> l1 = new ArrayList<>();List<Integer> l2 = new ArrayList<>();int len = nums1.length;for (int i = 0; i < len; i++){for (int j = 0; j < len; j++){l1.add(nums1[i] + nums2[j]);}}for (int i = 0; i < len; i++){for (int j = 0; j < len; j++){l2.add(nums3[i] + nums4[j]);}}int count = 0;for (int i : l1){for (int j : l2){if (i + j == 0) count++;}}return count;
}

实现过程中遇到哪些困难

无思路

看完代码随想录之后的想法

【解题思路】最暴力的解法：for循环四个数组，看看和是否为0（时间复杂度：O(n^4)）

思路和我的是一样的，不过我好像数据结构选错了，我用的List(ArrayList)，他用的Map(HashMap)，可以用Map的value值来存储元素重复出现的次数，就可以实现 “不去重” 的效果。

【想法】

1. 只能用Map，如果用List的话，无法计算重复的数据。例：

nums1 = [-1,-1] nums2 = [-1,1] nums3 = [-1,1] nums4 = [1,-1]

L1: [-2, 0, -2, 0] L2: [0, -2, 2, 0]

但输出：4 预期结果：6

看完视频自己写的ACC：

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {Map<Integer, Integer> m1 = new HashMap<>();Map<Integer, Integer> m2 = new HashMap<>();int len = nums1.length;for (int i = 0; i < len; i++){for (int j = 0; j < len; j++){if (m1.containsKey(nums1[i] + nums2[j])){int temp = m1.get(nums1[i] + nums2[j]);m1.put(nums1[i] + nums2[j], ++temp);}else {m1.put(nums1[i] + nums2[j], 1);}}}for (int i = 0; i < len; i++){for (int j = 0; j < len; j++){if (m2.containsKey(nums3[i] + nums4[j])){int temp = m2.get(nums3[i] + nums4[j]);m2.put(nums3[i] + nums4[j], ++temp);}else {m2.put(nums3[i] + nums4[j], 1);}}}int count = 0;for (Map.Entry<Integer, Integer> entry : m1.entrySet()) {if (m2.containsKey(-entry.getKey())){count += entry.getValue() * m2.get(-entry.getKey());}}return count;
}

标准答案ACC：map.getOrDefault(sum, 0) 好妙啊！

getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0;Map<Integer, Integer> map = new HashMap<Integer, Integer>();//统计两个数组中的元素之和，同时统计出现的次数，放入mapfor (int i : nums1) {for (int j : nums2) {int sum = i + j;map.put(sum, map.getOrDefault(sum, 0) + 1);}}//统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数for (int i : nums3) {for (int j : nums4) {res += map.getOrDefault(0 - i - j, 0);}}return res;}
}