云博
Leetcode 15 三数之和 (三指针解)

阅读量:(31) 您现在所在的位置: 首页 百宝箱 Leetcode Leetcode 15 三数之和 (三指针解) 作者:慎独、
简介:Leetcode 15 三数之和 ,三个指针对应3个数字,使用Timsort

题目:Leetcode 15. 三数之和 一刷(中等)

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

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/3sum


解题思路

一开始想使用暴力解法,时间复杂度接近O(n³),同时难以消除重复的组合,该方法失败。

后来又想了使用双指针+排序解决,从首尾分别向中间遍历,时间复杂度虽然降低了不少,但是同样难以消除重复的组合,因此 该方法也失败。

最后无奈参考了题解,发现需要用到三指针+排序实现。跟我的方法二的思想类似,只不过还需要一个指针来固定一个数, 动态的控制另外两个数。后来,按照题解的方法解出来后,仔细想了想,如果求两数之和等于0的所有不重复组合,两指针+排序也是轻松可以实现的。 那么推到三数之和,四数之和,是不是需要相对应的指针呢?虽然没有达到对于N数之和证明的实力,不过就先假设这个猜想成立吧。

本题解的关键点: 我总结了一句话,对于去掉重复的组合,最清晰的方法应该就是先排序,然后针对三个数字(三个指针) 都需要跳过相邻重复的数字。

时间复杂度平均为O(n²),空间复杂度为O(1)。


代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 三指针
        nums.sort()  # 时间杂度为O(NlogN)
        lens = len(nums)
        if lens < 3 or (nums[0] + nums[-1] > nums[-1] or nums[0] + nums[-1] < nums[0]):
            # 不可能有三元组满足a+b+c=0
            return []
        result = []
        for i in range(0,lens-2):
            if i > 0 and nums[i] == nums[i-1]: # 预防第一个数出现重复
                continue
            left, right = i+1, lens-1
            while left < right:
                if nums[i] + nums[left] + nums[right] == 0:
                # 因为两个数字已经能够决定第三个数字了,因此如果第一个数字固定,第二个也相同的话,则说明出现重复,因此在固定第一个数字后,要确保第二个数字不能重复,因此再排序好后需要跳过相同的相邻第二个数字
                    result.append([nums[i], nums[left] ,nums[right]])
                    # 动态修改双指针,对第二个数和第三个数进行预防重复,只需要跳过重复的数字
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    # 双指针向往下遍历
                    left += 1
                    right -= 1
                elif nums[i] + nums[left] + nums[right] > 0:
                    right -= 1
                else:
                    left += 1
        return result

点赞一波

0

    欢迎您游客

 小云标签


 网站统计:


笔记数: 总点赞量:

总访问量:   分类数目:

服务器:阿里云服务器

 网站动态: