LeetCode【0015】三数之和

本文目录

1 中文题目
2 求解思路
- 2.1 基础解法：暴力枚举法
- 2.2 优化解法：哈希表法
- 2.3 最优解法：双指针法
3 题目总结

1 中文题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组，输出三元组的顺序并不重要。

**示例 **

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。

输入：nums = [0,1,1]
输出：[]
解释：三数之和不为 0

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：有且只有一个三元组

提示：

$\leq nums.length \leq 3000$
$-10^5 \leq nums[i] \leq 10^5$

2 求解思路

2.1 基础解法：暴力枚举法

思路
使用三重循环遍历所有可能的三元组组合，找出满足和为0的组合。首先对数组进行排序，前面的数比后面的数字小，当前面的数大于0时，就可以提前跳出循环。最后对结果进行去重处理。

Python代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """
        暴力枚举法
        - 提前退出条件
        - 优化循环范围
        - 增加剪枝策略
        """
        if len(nums) < 3:
            return []
        
        # 对数组排序，便于剪枝
        nums.sort()
        n = len(nums)
        result_set = set()
        
        # 第一层循环
        for i in range(n-2):
            # 优化1：如果第一个数大于0，后面不可能和为0
            if nums[i] > 0:
                break
                
            # 第二层循环
            for j in range(i+1, n-1):
                # 优化2：如果前两个数之和大于0，第三个数更大，和一定大于0
                if nums[i] + nums[j] > 0:
                    break
                    
                # 第三层循环
                for k in range(j+1, n):
                    curr_sum = nums[i] + nums[j] + nums[k]
                    
                    # 优化3：根据和的大小提前退出
                    if curr_sum > 0:
                        break
                        
                    if curr_sum == 0:
                        result_set.add((nums[i], nums[j], nums[k]))
        
        return [list(x) for x in result_set]

时空复杂度分析

时间复杂度分析：O(n³)
- 三重循环：O(n³)
空间复杂度分析：O(n)

上面的代码，因为时间复杂度不能通过LeetCode的全部测试用例

2.2 优化解法：哈希表法

思路

将三数之和转化为两数之和加一个数，使用哈希表存储遍历过的数字，实现O(1)的查找。通过两层循环枚举两个数，然后在哈希表中查找第三个数，从而降低时间复杂度。

详细算法步骤：

预处理：
- 数组排序，便于去重和剪枝
- 处理特殊情况（长度小于3等）
外层循环（第一个数）：
- 遍历数组，固定第一个数
- 利用排序后的特性进行剪枝
- 处理重复元素
内层循环（第二个数）：
- 遍历第一个数之后的元素
- 使用哈希表存储已遍历的数
- 查找满足条件的第三个数
结果处理：
- 找到符合条件的组合后加入结果集，处理重复元素，确保结果不重复

python代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """
        哈希表解法
        1. 提前计算边界情况
        2. 更多的剪枝条件
        3. 优化哈希表使用方式
        """
        # 特判
        if len(nums) < 3:
            return []
            
        nums.sort()
        n = len(nums)
        res = []
        
        # 优化1:提前判断边界情况
        # 最小的三个数和大于0,或最大的三个数和小于0,直接返回
        if nums[0] + nums[1] + nums[2] > 0 or nums[-1] + nums[-2] + nums[-3] < 0:
            return []
            
        # 第一层循环,固定第一个数
        for i in range(n-2):
            # 第一个数大于0,后面不可能有解
            if nums[i] > 0:
                break
                
            # 去重
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            # 优化2:当前数字和可能的最小两个数和大于0,后面不可能有解
            if nums[i] + nums[i+1] + nums[i+2] > 0:
                break
                
            # 优化3:当前数字和可能的最大两个数和小于0,跳过当前数
            if nums[i] + nums[-1] + nums[-2] < 0:
                continue
                
            # 第二层循环,固定第二个数
            j = i + 1
            # 用set存储已经遍历过的数
            seen = set()
            
            while j < n:
                # 计算需要的第三个数
                target = -(nums[i] + nums[j])
                
                # 如果target在seen中,说明找到了答案
                if target in seen:
                    res.append([nums[i], nums[j], target])
                    # 去重:跳过重复的第二个数
                    while j + 1 < n and nums[j] == nums[j+1]:
                        j += 1
                        
                # 将当前数加入seen        
                seen.add(nums[j])
                j += 1
                
        return res

时空复杂度分析

时间复杂度：O(n²)
- 排序: O(nlogn)
- 两层循环: O(n²)
- 哈希表查找: O(1)
空间复杂度：O(n)
- 排序: O(logn)或O(n),取决于具体实现
- 哈希表: O(n)

2.3 最优解法：双指针法

思路
先对数组排序，固定一个数，然后用双指针在剩余部分寻找两个数，使三数之和为0。通过指针的移动来降低时间复杂度，同时利用排序后的特性进行剪枝和去重。核心思想是将问题转化为"一个固定数 + 两数之和"的形式，通过排序实现去重和双指针移动的条件，利用双指针减少一层循环，降低时间复杂度。

详细思路解析：

预处理阶段
- 对数组进行排序，使数组有序，排序后的数组便于去重和指针移动，排序后可以利用数组特性进行剪枝。
固定第一个数
- 从左到右枚举第一个数，固定一个数后，问题转化为两数之和。利用有序特性进行剪枝（第一个数大于0则结束）
双指针查找
- left指针从固定数右侧开始
- right指针从数组末尾开始
- 根据三数之和与0的关系移动指针：
  - 和大于0：右指针左移
  - 和小于0：左指针右移
  - 和等于0：记录结果并同时移动两个指针
去重处理
- 固定数去重：跳过相同的第一个数
- 左指针去重：跳过相同的左侧数
- 右指针去重：跳过相同的右侧数

python代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """
        使用双指针法求解三数之和问题
        
        参数:
            nums: 输入数组
        返回:
            满足和为0的三元组列表
        """
        # 处理特殊情况
        if len(nums) < 3:
            return []
            
        # 对数组进行排序，便于去重和使用双指针
        nums.sort()
        n = len(nums)
        result = []
        
        # 固定第一个数，遍历到倒数第三个数即可
        for i in range(n-2):
            # 优化1：如果第一个数大于0，后面的数都比它大，和不可能为0
            if nums[i] > 0:
                break
                
            # 优化2：跳过重复的第一个数，避免重复结果
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            # 双指针分别指向当前数后的两端
            left = i + 1
            right = n - 1
            
            # 双指针移动寻找满足条件的组合
            while left < right:
                curr_sum = nums[i] + nums[left] + nums[right]
                
                if curr_sum == 0:
                    # 找到满足条件的三元组
                    result.append([nums[i], nums[left], nums[right]])
                    
                    # 跳过重复的left值
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    # 跳过重复的right值
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                        
                    # 继续移动指针寻找其他组合
                    left += 1
                    right -= 1
                    
                elif curr_sum < 0:
                    # 和小于0，需要增加和，左指针右移
                    left += 1
                else:
                    # 和大于0，需要减少和，右指针左移
                    right -= 1
                    
        return result