每日一题 | LeetCode 454 四数相加Ⅱ
每日一题 | LeetCode 454 四数相加Ⅱ
题意
给你四个整数数组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:
示例 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】。文章转载请联系作者。
评论