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

每日一题 | LeetCode 454 四数相加Ⅱ
题意
给你四个整数数组nums1、nums2、nums3 和 nums4 ,数组长度都是n,请你计算有多少个元组 (i, j, k, l) 能满足:
0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例
示例 1:
示例 2:
题目解析
难度:中等
【三数之和】中写过,它的最优解是“排序 + 双指针”,强行用哈希解是为了练习哈希,为了不超时需要对各种细节的处理将难度拔高了一个 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 版本
Java 版本
版权声明: 本文为 InfoQ 作者【武师叔】的原创文章。
原文链接:【http://xie.infoq.cn/article/333303ae8849f169c142bd00d】。文章转载请联系作者。










评论