美文网首页程序员
leetCode.15 三数之和

leetCode.15 三数之和

作者: 半亩房顶 | 来源:发表于2019-03-09 23:46 被阅读9次

    题干

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

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

    例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
    满足要求的三元组集合为:
    [
    [-1, 0, 1],
    [-1, -1, 2]
    ]

    分析

    这个题目思路还是比较简单的,暴力肯定是要pass,肯定超时,所以需要就是尽力的优化时间复杂度。所有元素肯定都要用到,O(n)应该就是时间复杂度的极限了。如何一遍遍历,找出所有的结果?先给元素排个序就OK了。

    代码

    class Solution:
        def threeSum(self, nums: List[int]) -> List[List[int]]:
            nums.sort()
            res =[]
            i = 0
            for i in range(len(nums)):
                if i == 0 or nums[i]>nums[i-1]:
                    l = i+1
                    r = len(nums)-1
                    while l < r:
                        s = nums[i] + nums[l] +nums[r]
                        if s ==0:
                            res.append([nums[i],nums[l],nums[r]])
                            l +=1
                            r -=1
                            while l < r and nums[l] == nums[l-1]:
                                l += 1
                            while r > l and nums[r] == nums[r+1]:
                                r -= 1
                        elif s>0:
                            r -=1
                        else :
                            l +=1
            return res
    

    欢迎大家关注我的公众号


    半亩房顶

    相关文章

      网友评论

        本文标题:leetCode.15 三数之和

        本文链接:https://www.haomeiwen.com/subject/aisypqtx.html