写点什么

每日一题 | LeetCode 454 四数相加Ⅱ

作者:武师叔
  • 2022 年 6 月 03 日
  • 本文字数:1531 字

    阅读完需:约 5 分钟

每日一题 | LeetCode  454 四数相加Ⅱ

每日一题 | LeetCode 454 四数相加Ⅱ

题意

给你四个整数数组nums1nums2nums3 nums4 ,数组长度都是n,请你计算有多少个元组 (i, j, k, l) 能满足:


  • 0 <= i, j, k, l < n

  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例

示例 1:


输入:nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]输出:2解释:两个元组如下:1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 02. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
复制代码


示例 2:


输入:nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]输出:1
复制代码

题目解析

难度:中等


【三数之和】中写过,它的最优解是“排序 + 双指针”,强行用哈希解是为了练习哈希,为了不超时需要对各种细节的处理将难度拔高了一个 level,纯粹是吃饱了撑的自己搞自己。


而本道题则是哈希解法的亲儿子,有 4 个独立的数组,只要找出nums[i] + nums[j] + nums[k] + nums[l] = 0,同时题目也没要求找出不重复的四元组,这就不需要考虑去重,在难度上降了不少。


这道题知道了用哈希还不够,还需要做一下小处理。


不知大家还记不记得【两数之和】,遍历 nums 数组,对于当前元素nums[i],查询哈希表中是否存在 target - nums[i]


四数相加Ⅱ的解法可以将四数分为两组,即 “分组 + 哈希 ”


  • 初始化哈希表。 分组:nums1 和 nums2 一组,nums3 和 nums4 一组。 分别对nums1 和 nums2

  • 进行遍历,将所有 nums1 和 nums2的值的和作为哈希表的key,和的次数作为哈希表的value

  • 分别对 nums3 和 nums4进行遍历,若 -(nums1[k] + nums4[l])在哈希表中,则四元组次数 +hash[-(nums3[k]+nums4[l])] 次。

代码讲解

Python 版本

class Solution:    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
# 初始化哈希表 hash = {} cnt = 0
# 首先存储前两个数组之和 for n1 in nums1: for n2 in nums2: # 如果在哈希表中,则对应哈希值 +1 if n1 + n2 in hash: hash[n1 + n2] += 1 # 如果不在哈希表中,放入哈希表 else: hash[n1 + n2] = 1 # 统计剩余两个数组的和,在哈希表中找是否存在相加为 0 的情况。 for n3 in nums3: for n4 in nums4: if -(n3 + n4) in hash: cnt += hash[-(n3 + n4)]
return cnt
复制代码


Java 版本

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


发布于: 刚刚阅读数: 5
用户头像

武师叔

关注

每天丰富自己,去过自己想要的生活! 2022.04.28 加入

一个喜欢最新技术,研发的人工智能专业的大二学生,用自己的代码做一些有意义的事情! 目前大二结束有去大厂研发岗实习的计划,每天丰富自己的技术,去过自己想要的实习生活。

评论

发布
暂无评论
每日一题 | LeetCode  454 四数相加Ⅱ_哈希表_武师叔_InfoQ写作社区