15 三数之和.md

三数之和

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

1，必然是（两正一负，或 两负一正）；

2，两正一负，负的绝对值大于等于任何一个正数；两负一正，负的绝对值小于等于正数。

3，0放到那一边都可以。

思路一：正数组随意取出两个数，负数组取出一个数，反之亦然 。（做两个set，）

思路二：排序，取整数序列做成一个矩阵，负数序列也做成一个矩阵。两个矩阵相加，每个元素取相反数，与原来不同位置的元素比较是否相等。

方法一（双指针）：

如果固定一个数，三数之和就变成两数之和，此时可以用双指针。

具体：

• 固定第i个数，从第i+1和len(nums)-1这个范围中找，左右各一个指针，逐渐缩小。

难点：

• 过滤重复数据

def myTest(nums):

    #升序排列
    nums.sort()
    list = []
    
    
    for i in range(len(nums)):
        """
        A 从第一个数开始
        B 如果有重复的数，应该滤过。(nums[i]本应该大于nums[i-1]，
        但是当nums[i]==nums[i-1]时，条件为假，这个数不用，进行下一轮)
        """
        
        if i==0 or (nums[i]>nums[i-1]):

            left = i+1
            right = len(nums)-1

            while left<right:
                sum = nums[i]+nums[left]+nums[right]
                if sum==0:
                    list.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                    while left < right and nums[right] == nums[right+1]:
                        right -= 1
                elif sum>0:
                    right -= 1
                else :
                    left += 1
                    
                    
                    
    return list



print(myTest(nums))