大家好呀,我是帅蛋。
今天解决三数之和,这道题是面试中出现概率非常非常高的高频题。
对于这种类型的题一定要勤加练习,仔细揣摩。
话不多说,直接开始。
LeetCode 15:三数之和
题意
判断整数数组 nums 中是否存在三个元素 a、b、c,使得 a + b + c = 0。
要求:找出所有和为 0 且不重复的三元组
示例
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
提示
- 0 <= nums.length <= 3000
- -10^5 <= nums[i] <= 10^5
题目解析
超级好题,难度中等。
这道题用哈希的解法,可以参考之前我给大家讲【两数之和】时的思路,忘记的可以回顾一下:
两数之和是在数组中找出 a + b = target,每次枚举 a,找数组中有没有 target - b,即公式可以变成 b = target - a。
同样三数之和也可以用这个思路,既然是在数组中找出三元素 a + b + c = 0,那我们可以每次枚举 a,b,然后去数组中查询有无 -(a + b) 即可,即公式可以变成 c = -(a + b)。
通过两次 for 循环枚举 a 和 b 的值,然后用哈希在 O(1) 的时间去在一堆数中查找 -(a + b)。
思路其实说起来挺简单的,但是说实话,这道题用哈希来做的话,会把难度再提升一个 Level,不是在思路层面上,而是难在代码实现上。
毕竟两重 for 循环的时间复杂度就已经到 O(n²) 了,而且这道题要求找出“不重复”的三元组,那就要求要考虑到去重这步操作。
一些细节方面稍不注意,就容易 Time Limit Error(超时)。
图解
以 nums = [-1,0,1,2,-1,-4] 为例。
在开始之前,先对 nums 进行排序,并初始化一个结果集合。
# 对 nums 进行排序,这样在后面的时候可以减少重复带来的问题 nums.sort() # res 存储最后的结果,set 集合的特点是无序且无重复 res = set()
之后就是双重 for 循环找 a,b。
第 1 步,i = 0,此时 a 即 nums[0] = -4,初始化哈希表 hash:
(1)j = 1,b 即 nums[1] = -1,此时 b = -1 不在哈希表中,将 -(a+b)= 5 加入哈希表中。
for i in range(len(nums)): # 初始化哈希表。 hash = {} for j in range(i+1, len(nums)): # 如果不在哈希表中,加入哈希表 if nums[j] not in hash: hash[-nums[i]-nums[j]] = 1
这里我想特别说明一下,为什么把 -(a + b) 加到哈希表中,判断的是 b 不在哈希表中。
这个也算是个小技巧吧。
你想,如果 b 在哈希表中,那就证明此时 b 的值等于之前某一个 - (a + b) 的值,那就证明存在三个数相加等于 0。
为了看不晕,我把此时的 b 叫做 b1,之前 - (a + b) 中的 a 还是 a,b 还是 b。
那公式其实就成了 a + b + b1 = 0,即 b1 = -(a + b)。
这里的 b1 就是我们意义上的 c。
这里一定要仔细揣摩,很重要。
(2)j = 2,b 即 nums[2] = -1,此时 b = -1 不在哈希表中,将 -(a+b)= 5 加入 哈希表中(因为在哈希表中,值就为 1,而不是累加,所以和上图一样)。
直到 j = 5,都未发现等于零的三元组,此时数组及哈希表如下:
第 2 步,i = 1,此时 a 即 nums[1] = -1,初始化哈希表 hash:
(1)j = 2,b 即 nums[2] = -1,此时 b = -1 不在哈希表中,将 -(a+b)= 2 加入哈希表中。
(2)j = 3,b 即 nums[3] = 0,此时 b = 0 不在哈希表中,所以将对应 -(a + b) = 1 加入哈希表中。
(3)j = 4,b 即 nums[4] = 1,在哈希表中,此时的 a = nums[1] = -1,c = 此时的 b = 1,b = -(a + c) = 0。
# 如果在哈希表中,则存在三元组 else: res.add((nums[i],-nums[i]-nums[j],nums[j]))
(4) j = 5,b 即 nums[5] = 2,在哈希表中,此时的 a = nums[1] = -1,c = 此时的 b = 2,b = -(a + c)= 1。
第 3 步,i = 2,此时 a 即 nums[2] = -1,此时 a 的值和 nums[1] 的值相同,直接跳过即可。
为啥子呢?
因为 a = nums[1] 的时候已经和后面的都玩过了,腻了,不需要再玩一遍(因为还是一样的结果)。
# 元素去重 if i > 0 and nums[i] == nums[i -1]: continue
第 4 步,接下来的步骤和上面是一样的,答案已经全部找完,后面大家自己动手试一下。
代码实现
Python 代码实现
class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: # 如果 nums 个数 < 3,肯定组不成三元组 if len(nums) < 3: return [] # 对 nums 进行排序,这样在后面的时候可以减少重复带来的问题 nums.sort() # res 存储最后的结果,set 集合的特点是无序且无重复 res = set() for i in range(len(nums)): # 元素去重 if i > 0 and nums[i] == nums[i -1]: continue # 初始化哈希表。 hash = {} for j in range(i+1, len(nums)): # 如果不在哈希表中,加入哈希表 if nums[j] not in hash: hash[-nums[i]-nums[j]] = 1 # 如果在哈希表中,则存在三元组 else: res.add((nums[i],-nums[i]-nums[j],nums[j])) return list(res)
Java 代码实现
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); Arrays.sort(nums); for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { return result; } if (i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = nums.length - 1; while (right > left) { int sum = nums[i] + nums[left] + nums[right]; if (sum > 0) { right--; } else if (sum < 0) { left++; } else { result.add(Arrays.asList(nums[i], nums[left], nums[right])); while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; right--; left++; } } } return result; } }
图解三数之和到这就结束辣,是不是觉得难度有点不一样辣?
说点儿题外话,这道题其实最好的解法是“排序 + 双指针”,也比哈希法接起来简单且高效。
一题多解,用简单高效的方法解决掉这道题当然重要,但是我觉得更重要的是,你在碰到一个问题的时候能够多想一步,一步一步再一步,不同维度不同姿势都尝试一下。
刚开始这可能比较难,毕竟这涉及到一个改变,因为人都是有惰性的,毕竟只求一解比自找麻烦的求多解舒服多了...’
呃,希望小婊贝们能听进去,加油!