三数之和

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

def threeSum(nums):
    """
    双指针法，先对数组排序，然后选定第一个数后，左指针指向第一个数后边的数，右指针指向数组末尾，根据三个数的和，移动左指针或右指针。
    在移动指针时，跳过和当前所指的数重复的数，保证最后添加的三元组不重复
    """
    n = len(nums)
    if n < 3:
        return []
    
    result = []    
    nums.sort()
    i = 0
    while i < n - 2 and nums[i] <= 0:
        j = i + 1
        k = n - 1
        while j < k:
            three_sum = nums[i] + nums[j] + nums[k]
            if three_sum == 0:
                res = [nums[i], nums[j], nums[k]]
                result.append(res)
                k -= 1 # 成功添加一组满足条件的数后，移动左右指针
                j += 1
                while k > j and nums[k] == nums[k+1]:
                    k -= 1
                while j < k and nums[j] == nums[j-1]:
                    j += 1
            elif three_sum > 0: # 如果和大于0，移动右指针
                k -= 1
                while k > j and nums[k] == nums[k+1]: # 跳过重复的数
                    k -= 1
            else:
                j += 1
                while j < k and nums[j] == nums[j-1]:
                    j += 1
        i += 1
        while i < n - 2 and nums[i] == nums[i-1]:
            i += 1
            
    return result

三数之和

原文：https://www.cnblogs.com/youguang369/p/14477704.html