15 三数之和

题目链接：15. 三数之和

解题思路

方法一：暴力解法（哈希表）

锁定第一个数之后，问题转化为经典的**“两数之和”**：寻找剩余的两个数，使它们相加等于第一个数的相反数。

但此题与普通两数之和存在两点主要差异，这也是题目的核心难点：

1. 不能有重复的三元组：为了方便后续结果去重，在操作前必须先对数组进行升序排序。
2. 需要跳过重复元素：在遍历锁定第一个数，以及寻找另外两个数时，如果遇到与前一个相同的数字，必须跳过以进行去重，否则会记录重复的解。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ans = []

        for i in range(len(nums)):
            if nums[i] > 0:
                break

        # 先对拿到的这个数去重
            if i> 0 and nums[i] == nums[i-1]:
                continue
    
            target = -nums[i]
            visited = set()

            j = i + 1
            while j < len(nums):
                fin = target - nums[j]
                if fin in visited:
                    ans.append([nums[i],nums[j],fin])
                    while j + 1 < len(nums) and nums[j] == nums[j + 1]:
                        j += 1
                visited.add(nums[j])
                j += 1
        return ans

性能分析：这种基于哈希表的方法整体时间复杂度为 $O(n^2)$，维护 set 集合的插入和查找存在常数级耗时；此外还需要开辟哈希表储存元素，空间复杂度为 $O(n)$。

方法二：排序 + 双指针解法（最优解）

既然第一步已经将数组排序，对于有序数组，可以使用双指针寻找另外两数。

双指针解法的外层框架和上述思路一致：通过遍历锁定第一个数 nums[i]。主要区别在于，内层寻找另外两个数时，使用左右双指针 L 和 R 向中间逼近，从而将空间复杂度降至 $O(1)$。

双指针移动逻辑：

• 如果 sum == 0：找到一组满分解，记录该组合。随后 L 右移，R 左移。注意：移动时需要使用 while 循环跳过所有相邻的重复数字，避免重复解。
• 如果 sum < 0：当前三数之和偏小。由于数组递增，需要让左指针 L 右移，以增大两数之和。
• 如果 sum > 0：当前三数之和偏大。同理，需要让右指针 R 左移，以减小两数之和。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        List = []
        l = len(nums)
        if not nums or l < 3:
            return List
        nums.sort()
        for i in range(l):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i-1]:
                continue
            L = i + 1
            R = l - 1
            while(L < R):
                sum = nums[L] + nums[R] + nums[i]
                if sum == 0:
                    List.append([nums[L], nums[R], nums[i]])
                    while L<R and nums[L] == nums[L+1]:
                        L += 1
                    while L<R and nums[R] == nums[R-1]:
                        R -= 1
                    L += 1
                    R -= 1
                elif sum < 0:
                    L += 1
                elif sum >0:
                    R -= 1
        return List

执行耗时约为 615ms，击败了 49.35% 的测试通过率。

虽然双指针将空间复杂度优化至 $O(1)$，但时间复杂度依旧是 $O(n^2)$。处理大规模数组时，可以通过剪枝策略进一步提升效率。

进阶优化：剪枝策略

在最外层固定选定数 nums[i] 的循环中，加入剪枝判断能有效减少无效遍历：

1. 最小和判断：因数组已排序递增，若当前固定的数与紧邻的两个数之和 nums[i] + nums[i+1] + nums[i+2] > 0，由于后续的数字只会更大，不可能再凑成 0。此时可直接 break 结束外层循环。
2. 最大和判断：若当前固定的数与最后最大的两个数之和依然小于 0，即 nums[i] + nums[-1] + nums[-2] < 0，说明当前 nums[i] 过小，本轮无法凑成 0，可直接 continue 跳至下一个 i。