三数之和python(leetcode15)

三数之和python(leetcode15)

#15. 三数之和

示例 ：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

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

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # n的范围 0 <= nums.length <= 3000
        # 答案中不可以包含重复的三元组
        
        n = len(nums)
        record = []
        nums = sorted(nums)
        if(n < 3):
            return []
        for i in range(n):
            if nums[i] > 0:
                return record
            # nums[i]=nums[i-1]时，结果会和上一个元素的结果相同
            if (i > 0 and nums[i] == nums[i - 1]):
                continue
            l, r = i + 1, n - 1
            while(l < r):
                sum0 = nums[i] + nums[l] + nums[r]
                if sum0 == 0:
                    record.append([nums[i], nums[l], nums[r]])
                    # 需要去重操作
                    while(l < r and nums[l] == nums[l + 1]):
                        l += 1
                    while(l < r and nums[r] == nums[r - 1]):
                        r -= 1
                    l += 1
                    r -= 1
                elif sum0 < 0:
                    l += 1
                else:
                    r -= 1
        return record