本文共 2335 字，大约阅读时间需要 7 分钟。

01 题目：三数之和

链接：https://leetcode-cn.com/problems/3sum

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

示例：

[

  [-1, 0, 1],

  [-1, -1, 2]

]

02 解析

1. 先从小到大排序：sort()函数
2. 参数初始化：k从0到 len(nums)-2就够了，题里说的是a,b,c三个不同的数；i=0，j=len(nums)-1开始
3. 保持指针k（蓝色）不动：先移动指针 i (小->大 橙色)，移动指针 j(大->小 绿色)
   并计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集
4. 判断+去重：
   第一个if：如果 nums[ k ]大于 0，则三数之和一定 0，结束循环
   第二个if：如果 nums[ k ] = nums[ k-1 ]，则说明该数字重复，会导致结果重复，所以应该跳过
   第三个if：计算sum
       当 sum < 0 时, i++；若nums[ i ]= nums[ i+1 ]，则会导致结果重复，应该跳过，i++
       当 sum > 0 时, j–；若nums[ j ]= nums[ j-1 ] 则会导致结果重复，应该跳过，j−−
       同理，当 sum = 0 时，res.append([nums[k], nums[i], nums[j]])
             若 nums [i ]= nums[ i+1 ]则会导致结果重复，应该跳过，i++
             若 nums[ j ]= nums[ j-1] 则会导致结果重复，应该跳过，j−−
   
   时间复杂度：O(n²)，n 为数组长度

03 代码

def threeSum(nums):    nums.sort() # 排序    res, k = [], 0    for k in range(len(nums) - 2):        if nums[k] > 0: break # 1. because of j > i > k.        if k > 0 and nums[k] == nums[k - 1]: continue # 2. skip the same `nums[k]`.        i, j = k + 1, len(nums) - 1        while i < j: # 3. double pointer            s = nums[k] + nums[i] + nums[j]            if s < 0:                i += 1                while i < j and nums[i] == nums[i - 1]: i += 1            elif s > 0:                j -= 1                while i < j and nums[j] == nums[j + 1]: j -= 1            else:                res.append([nums[k], nums[i], nums[j]])                i += 1                j -= 1                while i < j and nums[i] == nums[i - 1]: i += 1                while i < j and nums[j] == nums[j + 1]: j -= 1    return res    # 作者：jyd    # 链接：https://leetcode-cn.com/problems/3sum/solution/3sumpai-xu-shuang-zhi-zhen-yi-dong-by-jyd/

自个第一次写这个函数的时候，没考虑到去重，而是在得出所有符合三数之和为0的组合后，才去重的。

'''嵌套列表去重方法直接看[22]会有点懵,先看20, 它将a的每个小列表先转成元组,再去重,然后变成列表再看[22],后半部分是完成了元组-去重,前部分将每个小元组变成列表,再变成大列表,但是是乱序的最后是[25],sort方法通过参数key指定索引值,故指定a的下标,根据这个索引,对new列表进行排序'''In [19]: a = [[0,0,0,],[4,2,5],[1,8,6],[0,0,0],[5,3,9],[4,2,5]]In [20]: new = list(set(tuple(i) for i in a))In [21]: newOut[21]: [(5, 3, 9), (4, 2, 5), (0, 0, 0), (1, 8, 6)]In [22]: new = [list(t) for t in set(tuple(i) for i in a)]In [23]: newOut[23]: [[5, 3, 9], [4, 2, 5], [0, 0, 0], [1, 8, 6]]In [24]: new.sort(key = a.index)In [25]: newOut[25]: [[0, 0, 0], [4, 2, 5], [1, 8, 6], [5, 3, 9]]

转载地址：http://bujii.baihongyu.com/