题目

显然可以三个for暴力

但是显然会超时。不过在刷题的时候可以先试试，反正30秒就写完。

双指针

首先一个小技巧，可以先对数组sort一下，让他从小到大排列。

不重复，首先要保证i

注意的是，左侧起点是i+1，因为i从左往右遍历，数字都已经遍历过了，j再从头开始会重复。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums=sorted(nums)
        res=[]
        length=len(nums)
        for i in range(length):
            # 俩指针，一个从前面走，一个从后面走。
            j,k=i+1,length-1
            while j<k:
                if nums[i]+nums[j]+nums[k]==0:
                    res.append([nums[i],nums[j],nums[k]])
                    break
                elif nums[i]+nums[j]+nums[k]<0:
                    j+=1
                else:
                    k-=1
        
        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

结果
好家伙，虽然j k指针不一样，但是数值是一样的。
怎么避免这种情况，直接continue掉呢？

去重

好家伙，费了不少功夫。
既然去重要数字不同的，那假设i j k的任意相邻数字相同，我就跳过他，只记录一个相同的数字。
对i来说，在for的时候向后找即可；
对j来说，只保留最后一个不相同的，其他的全部j+=1掉，不要再次找到了；
对k来说，也是只保留最前面一个不相通的，其他的k-=1掉，不要再次找到。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums=sorted(nums)
        res=[]
        length=len(nums)
        for i in range(length):
            # 前面至少保留一个，前界要从最后一个开始
            if(i>0 and nums[i]==nums[i-1]):
                continue
            # 俩指针，一个从前面走，一个从后面走。
            j,k=i+1,length-1
            while j<k:
                if nums[i]+nums[j]+nums[k]==0:
                    res.append([nums[i],nums[j],nums[k]])
                    
                    # 从最后一个这个元素开始再找。
                    while  j<k and nums[j]==nums[j+1]:
                        j+=1
                    # 此时nums[j]已经的下一个已经不和原先一样了，但是nums[j]还是一样的，要再走一步
                    j+=1
                    while j<k and nums[k]==nums[k-1]:
                        k-=1
                    # 同理也要再走一步
                    k-=1
                    
                elif nums[i]+nums[j]+nums[k]<0:
                    j+=1
                else:
                    k-=1
        
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31