15. 三数之和

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

思路

• 对于数组 nums，如果它的长度小于 3，返回 []。
• 对数组排序；
• 遍历之后排序数组：
  • 若 nums[i]>0 ：因为已经排序好，后面不可能有 3 个数加和为 0，返回结果。
  • 对重复元素跳过，避免出现重复解。
  • 令左指针 L=i+1，右指针 R=n-1，当 L<R 时，执行循环：
    • 若 nums[i]+nums[L]+nums[R]==0 时，判断这个解是否重复，并进入下一循环
    • 若和大于 0，说明 nums[R] 太大，左移 R
    • 若和小于 0，说明 nums[L] 太小，右移 L

最终代码：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []
        nums.sort()
        ts = []
        lnums = len(nums)
        for i, num in enumerate(nums):
            if num > 0:
                return ts
            # skip same numbers
            if i > 0 and num == nums[i-1]:
                continue
            l, r = i+1, lnums-1
            while l < r:
                su = num+nums[l]+nums[r]
                if su==0:
                    ts.append([num, nums[l], nums[r]])
                    # skip same l and r
                    while l<r and nums[l]==nums[l+1]:
                        l+=1
                    while l<r and nums[r-1]==nums[r]:
                        r-=1
                    l, r = l+1, r-1
                elif su > 0:
                    r-=1
                else:
                    l+=1
        return ts

想得太多