题解 | #三数之和#

1.双指针遍历

class Solution:
    def threeSum(self, num: List[int]) -> List[List[int]]:
        if len(num) < 3:
            return []
        num.sort()
        res, i = set(), 0
        # 外层目标指针循环 用while可以跳过重复的目标值
        while i < len(num):
            # 定义左右指针指向头尾
            left, right = 0, len(num) - 1
            # 双指针开始循环
            while left < right:
                # 若目标指针与左指针重叠则跳过
                if i == left:
                    left += 1
                # 若目标指针与右指针重叠则跳过
                elif i == right:
                    right -= 1
                # 若目标值与左右指针值和为0,则排序后将元组记入集合res
                elif num[i] + num[left] + num[right] == 0:
                    t = [num[i], num[left], num[right]]
                    t.sort()
                    res.add(tuple(t))
                    left += 1
                    right -= 1
                # 小于0,左指针右移
                elif num[i] + num[left] + num[right] < 0:
                    # 加速左指针右移,跳过重复值
                    while left + 1 < right and num[left + 1] == num[left]:
                        left += 1
                    left += 1
                # 大于0,左右指针左移
                elif num[i] + num[left] + num[right] > 0:
                    # 加速右指针左移,跳过重复值
                    while right - 1 > left and num[right - 1] == num[right]:
                        right -= 1
                    right -= 1
            # 加速目标指针右移,跳过重复值
            while i + 1 < len(num) and num[i + 1] == num[i]:
                i += 1
            i += 1
        # 将set中的元组转化为列表
        result = []
        while res:
            result.append(list(res.pop()))
        return result

2.分类讨论,分为全零/正负零/正正负/正负负进行讨论

class Solution:
    def threeSum(self, num: List[int]) -> List[List[int]]:
        if len(num) < 3:
            return []
        # 记录去重后的正数/负数以及0的个数
        numz,numf,num0= set(),set(),0
        # 记录每个数字出现个数
        hashset = {}
        # 遍历分组
        for i in num:
            if i in hashset:
                hashset[i] += 1
            else:
                hashset[i] = 1
            if i > 0:
                numz.add(i)
            elif i < 0:
                numf.add(i)
            else:
                num0 += 1
        # 转为列表快排
        numz,numf = list(numz),list(numf)
        numz.sort()
        numf.sort()
        # 定义最终集合rst
        rst = set()
        # 取0,0,0时
        if num0 >= 3:
            rst.add(tuple([0, 0, 0]))
        # 取正,负,0
        if num0 > 0:
            # 定义正数数组numz左指针,定义负数数组numf右指针
            left,right = 0,len(numf) - 1
            # 双指针开始遍历
            while left < len(numz) and right >= 0:
                if numz[left] + numf[right] == 0:
                    # 指定顺序为负,0,正
                    rst.add(tuple([numf[right], 0, numz[left]]))
                    left += 1
                    right -= 1
                elif numz[left] + numf[right] < 0:
                    left += 1
                elif numz[left] + numf[right] > 0:
                    right -= 1
        # 取正,正,负
        for i in range(len(numz)):
            for j in range(len(numf)):
                # 定义目标值t
                t = -numf[j] - numz[i]
                # 若t为非正数,直接跳过
                if t <= 0:
                    continue
                # 若t不在hashset中,直接跳过
                if t in hashset:
                    # 若t与正数不相同
                    if t != numz[i]:
                        # 指定从小到大的顺序
                        if numz[i] > t:
                            rst.add(tuple([numf[j], t, numz[i]]))
                        else:
                            rst.add(tuple([numf[j], numz[i], t]))
                    # 若t与正数相同,判断数组***有几个t,避免一值多用
                    else:
                        if hashset[t] > 1:
                            rst.add(tuple([numf[j], numz[i], t]))

        # 取负负正 过程同上
        for i in range(len(numf)):
            for j in range(len(numz)):
                t = -numz[j] - numf[i]
                if t >= 0:
                    continue
                if t in hashset:
                    if t != numf[i]:
                        if t < numf[i]:
                            rst.add(tuple([t, numf[i], numz[j]]))
                        else:
                            rst.add(tuple([numf[i], t, numz[j]]))
                    else:
                        if hashset[t] > 1:
                            rst.add(tuple([numf[i], t, numz[j]]))
        # 将set中的元组转化为列表
        result = []
        while rst:
            result.append(list(rst.pop()))
        return result