力扣Leetcode：15. 三数之和（Python）

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

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

我们可以很自然地想到通过三重循环遍历，那么时间复杂度达到O(N³)。但有一个问题没办法解决——没法判断是否是重复的三元组。这一问题不能通过简单的去重解决，因为一个三元组中允许出现相同的元素，比如[-1,-1,2]。

对于三重循环，什么时候会得到重复的三元组呢？当枚举的前两个数不变时，那么第三个数必然也不变，三元组就会重复。那么分析到这里就有了一种思路——

• 对于在同一个最外层循环内，即固定了第一个数字时，不要枚举重复的第二个数字。
• 不要枚举相同的第一个数字。
• 允许第一个数字与第二个数字重复。

为了保证上面这三点，一个很简单的方案就是排序。对于有序数组，避免元素重复仅需和前一个元素比较即可。

接下来我们来考虑时间复杂度的优化。前两层循环似乎没有什么可以优化的地方了，但对于第三层循环，我们可以充分考虑到数组的有序性，每当固定i增大j时，k必然减小，因此从右向左枚举k即可，第三层循环与第二层循环是并列的，并不需要嵌套。这样的处理可以将时间复杂度将为O(N²)。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        rs, n = [], len(nums)
        if n < 3:
            return rs
        nums.sort()
        for i in range(n):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            k = n - 1
            for j in range(i+1, n):
                if j > i+1 and nums[j] == nums[j-1]:
                    continue
                while k > j and nums[i] + nums[j] + nums[k] >= 0:
                    if nums[i] + nums[j] + nums[k] == 0:
                        rs.append([nums[i], nums[j], nums[k]])
                        break
                    k -= 1
        return rs