LeetCode50天刷题计划（Day 10—— 三数之和（20.50-22.40）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

世界上最简单也最困难的事情，就是坚持

一、题目

三数之和

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

示例

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

示例 2：
输入：nums = []
输出：[]

示例 3：
输入：nums = [0]
输出：[]

提示

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

二、思路

一开始想用暴破，并一开始就采用将数组排序的方法，按顺序查找，以此去重，但是优化后也有三个测试点过不去，因此选用双指针法：

如果每轮循环固定第一个元素a，那么只需要找到两数之和等于-a的两个元素b和c，那么此三元组求和为某值的问题就退化为两元组求和

注意：每次a固定时，b和c可能有多组解。由于数组是有序的，初始时，b指针指向a后元素，c指针指向末尾元素，并始终维持b<c(不重复）
如果b+c小于所需值，就使b后移令其和增加；如果b+c小于所需值，就使c左移令其和减小，直至b和c相遇.

三、代码

1.没过的暴破（python）

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        #排序,保证输出从小到大
        nums.sort()
        #整数个数
        n=len(nums)
        #结果数组
        re_list=[]
        if n<3 :
            return re_list
        #暴破
        for i in range(n-2):
            for j in range(i+1,n-1):
                temp=nums[i]+nums[j]
                for k in range(j+1,n):
                    if(temp== -nums[k] and [nums[i],nums[j],nums[k]] not in re_list):
                        re_list.append([nums[i],nums[j],nums[k]])
        return re_list

2.AC的双指针（python）

实在不知道咋去重，估计if([nums[i],nums[j],nums[k]] not in re_list): #去重很费时间，但好歹过了，能跑就行（嘻）

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()#排序,保证输出从小到大[-4,-1,-1,0,1,2]，这是解题重点！！
        n=len(nums)#整数个数
        re_list=[]#结果数组
        if n<3 :
            return re_list
        #暴破（可以优化为双指针，因为在有序情况下，第二个指针后移时第三指针必须要前移，才能保证为0）
        for i in range(n-2):
            j=i+1 #j，第二个数的指针，从前向后移动
            k=n-1 #k，第三个数的指针，从后往前移动
            while(j<k):
                if(nums[j]+nums[k]<-nums[i]):
                    j+=1 #移动j
                elif(nums[j]+nums[k]>-nums[i]):
                    k-=1 #移动k
                else:
                    if([nums[i],nums[j],nums[k]] not in re_list): #去重
                        re_list.append([nums[i],nums[j],nums[k]]) #bingo
                    j+=1
        return re_list