Leetcode - 15.三数之和( 两数之和的升级版?)

如果你时间比较紧迫,为了找工作而刷题,我建议你先刷热门推荐,一共100道题。

先刷热题 HOT 100,再刷精选 TOP 面试题,之后刷其他的题。

接下来的一段时间,我会把做的这些题做一个总结,每天在  每日一题算法群 中公布题目和解法,定时推送公众号,欢迎各位关注公众号加入群聊,大家一起监督一起努力。

Leetcode - 15.三数之和

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4]

满足要求的三元组集合为:[ [-1, 0, 1], [-1, -1, 2]]

两数之和

我们先回忆一下两数之和是怎么做的?两数之和众的暴力做法是嵌套两层循环,这样的话,复杂度是 n^2 ,由于添加了哈希表这种带有 备忘录 形式的数据结构,使得我们的算法复杂度可以到n。

三数之和

我们现在考虑一下暴力法怎么做的?最简单的方法就是暴力法嵌套三层循环,然后找到最终的答案,那么最坏的复杂度就是n^3.

如果说我们考虑用哈希表去存储一个结果,那么可以将我们的复杂度降低到n^2,显然这个复杂度也是比较大的,而且其中如果有一些重复的元素的话,要另外处理,代码比较冗余了。

我们可以先把这个数组进行从小到大的排序,因为排序的复杂度 O(NlogN)  是远远小于n^2的,排序后,你会发现,由于三数之和是等于零,那么如果当前这个元素是大于零的话,而且,这个数组是按照从小到大排序的话,那么当前这个元素作为起点的集合是为空的,因为后面的元素都是比这个元素大的元素,是不可相加等于零。

由此我们可以节省一些复杂度,当然,我们进行排序的时候,是要经历一些复杂度的,但这远远小于n的平方,所以我们这个做法还是比较快的

然后我们在确定起点之后,通过双指针去遍历其他两个元素。双指针详情见 盛最多水的容器(双指针) 这道题目

由于整个数组是有序的,那么我们在遍历的时候,两个指针可以通过三数之和的结果来判断。

  • 如果是大于零,那么说明们的j指针往左移。

  • 如果小于零,说明我们的i指针往左移动。

  • 恰好等于零那么我们就输出结果

时间复杂度:O(N^2) 

空间复杂度:O( 1 )

class Solution:

def threeSum(self, nums: List[int]) -> List[List[int]]:

nums.sort()

res = []


for k in range(len(nums) - 2):

if nums[k] > 0: break # k后面的数肯定大于零,跳出循环

if k > 0 and nums[k] == nums[k - 1]: continue

i, j = k + 1, len(nums) - 1

while i < j:

if nums[i] + nums[j] + nums[k] == 0:

res.append([nums[i], nums[j], nums[k]])

i += 1

j -= 1

while nums[i] == nums[i-1] and i < j:i += 1 # 相同的数跳过

while nums[j] == nums[j+1] and i < j:j -= 1 # 相同的数跳过

elif nums[i] + nums[j] + nums[k] < 0:

i += 1

while nums[i] == nums[i-1] and i < j:i += 1

else:

j -= 1

while nums[j] == nums[j+1] and i < j:j -= 1

return res


LeetCode day 1 题号1、2(两数之和,两数相加)

LeetCode day 2 题号 3、4 (最长无重复子串,两个有序数组的中位数)

LeetCode day3 题号5 (最长回文子串)

LeetCode day 4  10.正则匹配

LeetCode day 5 盛最多水的容器(双指针)

快来加入  每日一题算法群

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章