Leetcode: 15. 三数之和 python 2020.2.10

69 阅读 0 评论 46 点赞

我是靠谱客的博主甜美皮卡丘，最近开发中收集的这篇文章主要介绍Leetcode: 15. 三数之和 python 2020.2.10，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

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

示例：

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        length = len(nums)
        if(length < 3):   
            return []

        nums = sorted(nums)  #nums.sorted()
        res = []

        for i in range(length):
            if(nums[i] > 0):   #排序后第一个数都大于0的话，则后面的数肯定都大于0，肯定不满足条件
                break
            if(i > 0 and nums[i]==nums[i-1]):  #避免重复的
                continue

            low = i+1
            high = length-1

            while(low < high):
                #print(i,low,high)
                sum = nums[i]+nums[low]+nums[high]
                if(sum == 0):
                    res.append([nums[i],nums[low],nums[high]])
                    high-=1
                    low+=1

                    while(low < high and low > i+1 and nums[low] == nums[low-1]):  #避免判断重复的
                        low+=1
                    while(low < high and high < length-1 and nums[high] == nums[high+1]):  #避免判断重复的
                        high-=1
                elif(sum > 0):
                    high-=1
                else:
                    low+=1
                
        return res