leetcode刷题笔记——15.三数之和

一、问题描述

给定一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]]，使得：

• i != j、i != k 且 j != k

• nums[i] + nums[j] + nums[k] == 0

需要返回所有和为 0 的三元组，且这些三元组不能重复。

输入输出

• 输入: 整数数组 nums

• 输出: 包含所有和为 0 的不重复三元组的列表

示例

1. 输入: nums = [-1,0,1,2,-1,-4]
   输出: [[-1,-1,2],[-1,0,1]]
   解释：存在两个不同的三元组，它们的和均为 0。

2. 输入: nums = [0,1,1]
   输出: []
   解释：不存在三元组的和为 0。

3. 输入: nums = [0,0,0]
   输出: [[0,0,0]]
   解释：唯一的三元组和为 0。

注意事项

• 输出的顺序和三元组内部的顺序不重要。

• 需确保返回的三元组不重复。

二、解题思路以及代码实现

方法 1: 排序 + 双指针法

解题思路

1. 排序: 首先对输入数组进行排序。这是因为在有序数组中，可以使用双指针法更有效地查找三元组。

2. 遍历数组: 使用一个 for 循环遍历每个元素 nums[i]，确保 nums[i] 是当前处理的元素（避免重复）。如果 nums[i] 大于 0，由于数组是有序的，后面的数都将更大，所以可以结束循环。

3. 双指针: 对于每个选定的 nums[i]，设置两个指针：left 指向 i+1，right 指向数组末尾。计算三数之和 current_sum = nums[i] + nums[left] + nums[right]。

   1. 如果 current_sum 为 0，保存该三元组，并移动 left 和 right 指针，跳过重复的元素。

   2. 如果 current_sum 小于 0，移动 left 指针向右。

   3. 如果 current_sum 大于 0，移动 right 指针向左。

时间复杂度

• 排序: O(n log n)排序不管是分治排序还是快排的时间复杂度都是 O(n log n)，详细可以搜搜

• 双指针遍历: O(n²)

• 总时间复杂度: O(n log n + n²) = O(n²)

空间复杂度

• O(k)，其中 k 是输出中三元组的数量（额外空间用于结果存储）。

代码实现

def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()  # 排序result = []n = len(nums)for i in range(n):if i > 0 and nums[i] == nums[i - 1]:  # 跳过重复元素continueleft, right = i + 1, n - 1while left < right:current_sum = nums[i] + nums[left] + nums[right]if current_sum == 0:result.append([nums[i], nums[left], nums[right]])# 跳过重复元素while left < right and nums[left] == nums[left + 1]:left += 1while left < right and nums[right] == nums[right - 1]:right -= 1left += 1right -= 1elif current_sum < 0:left += 1else:right -= 1    return result

方法 2: 哈希表法

解题思路

1. 使用哈希表: 利用一个哈希集合来存储每个元素，帮助快速查找。

2. 遍历: 对于数组中的每个元素 nums[i]，需要找到另外两个数 nums[j] 和 nums[k]，使得 nums[i] + nums[j] + nums[k] = 0。这可以转化为寻找 -nums[i] = nums[j] + nums[k]。

3. 双重循环: 使用双重循环遍历数组中的所有可能的组合，计算 target = -nums[i]，然后检查哈希表中是否存在可以与 nums[j] 组合成 target 的元素 nums[k]。

4. 避免重复: 使用一个集合存储找到的三元组，确保输出中不包含重复的三元组。

时间复杂度

• 外层循环: O(n)，内层循环: O(n)

• 哈希表查找: O(1)

• 总时间复杂度: O(n²)

空间复杂度

• O(n)，用于存储哈希表和结果集合。

代码实现

def threeSum(nums):result = set()n = len(nums)for i in range(n):target = -nums[i]seen = set()for j in range(i + 1, n):complement = target - nums[j]if complement in seen:result.add((nums[i], nums[j], complement))seen.add(nums[j])return [list(triplet) for triplet in result]