三数之和

三数之和_牛客题霸_牛客网

问题简述

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。

思路

• 排序；

• 先确定第一个数；

• 剩下两个数通过一组双指针分别从两端对向遍历；

• 难点：去重

  • 首先第一个数需要去重；

  • 双指针遍历的时候也要去重；

• 详见代码；

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def threeSum(self , arr: List[int]) -> List[List[int]]:
        
        arr.sort()
        N = len(arr)
        
        ret = []
        
        for i in range(N):
            # 去重1
            if i > 0 and arr[i] == arr[i - 1]:
                continue
            
            # 下面相当于求“两数之和”
            target = -arr[i]
            # 初始化双指针：闭区间
            l, r = i + 1, N - 1
            # 退出循环时 l == r
            while l < r:
                v = arr[l] + arr[r]
                if v < target:
                    l += 1
                elif v > target:
                    r -= 1
                else:
                    ret.append([arr[i], arr[l], arr[r]])
                    # 去重2
                    while l < r and arr[l] == arr[l + 1]: l += 1
                    while l < r and arr[r] == arr[r - 1]: r -= 1
                    # 退出循环时，l,r 停在最后一个相同的数字上，所以还要走一步
                    l += 1
                    r -= 1
        
        return ret