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 的不重复三元组的列表
示例
-
输入:
nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释：存在两个不同的三元组，它们的和均为 0。 -
输入:
nums = [0,1,1]
输出:[]
解释：不存在三元组的和为 0。 -
输入:
nums = [0,0,0]
输出:[[0,0,0]]
解释：唯一的三元组和为 0。
注意事项
-
输出的顺序和三元组内部的顺序不重要。
-
需确保返回的三元组不重复。
二、解题思路以及代码实现
方法 1: 排序 + 双指针法
解题思路
-
排序: 首先对输入数组进行排序。这是因为在有序数组中，可以使用双指针法更有效地查找三元组。
-
遍历数组: 使用一个
for循环遍历每个元素nums[i]，确保nums[i]是当前处理的元素（避免重复）。如果nums[i]大于 0，由于数组是有序的，后面的数都将更大，所以可以结束循环。 -
双指针: 对于每个选定的
nums[i]，设置两个指针：left指向i+1，right指向数组末尾。计算三数之和current_sum = nums[i] + nums[left] + nums[right]。-
如果
current_sum为 0，保存该三元组，并移动left和right指针，跳过重复的元素。 -
如果
current_sum小于 0，移动left指针向右。 -
如果
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: 哈希表法
解题思路
-
使用哈希表: 利用一个哈希集合来存储每个元素，帮助快速查找。
-
遍历: 对于数组中的每个元素
nums[i]，需要找到另外两个数nums[j]和nums[k]，使得nums[i] + nums[j] + nums[k] = 0。这可以转化为寻找-nums[i] = nums[j] + nums[k]。 -
双重循环: 使用双重循环遍历数组中的所有可能的组合，计算
target = -nums[i]，然后检查哈希表中是否存在可以与nums[j]组合成target的元素nums[k]。 -
避免重复: 使用一个集合存储找到的三元组，确保输出中不包含重复的三元组。
时间复杂度
-
外层循环: 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]