LeetCode 15. 3Sum 题解

LeetCode 15. 3Sum 题解题目描述给你一个整数数组nums判断是否存在三元组[nums[i], nums[j], nums[k]]满足i ! j、i ! k且j ! k同时还满足nums[i] nums[j] nums[k] 0。请你返回所有和为 0 且不重复的三元组。注意答案中不可以包含重复的三元组。示例 1输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]]示例 2输入nums [] 输出[]示例 3输入nums [0] 输出[]解题思路方法排序 双指针思路首先对数组进行排序这样可以方便地使用双指针来查找遍历数组中的每个元素作为三元组的第一个元素如果当前元素大于 0由于数组已经排序后面的元素都大于 0不可能和为 0直接返回结果如果当前元素与前一个元素相同跳过避免重复使用双指针分别指向当前元素的下一个元素和数组的最后一个元素计算三个元素的和如果和等于 0将这三个元素添加到结果中然后移动左右指针跳过重复的元素如果和小于 0左指针右移如果和大于 0右指针左移复杂度分析时间复杂度O(n²)其中 n 是数组的长度。排序的时间复杂度是 O(n log n)遍历和双指针的时间复杂度是 O(n²)。空间复杂度O(1)只需要常数级的额外空间不考虑存储结果的空间。代码实现方法排序 双指针class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: n len(nums) if n 3: return [] # 排序 nums.sort() result [] for i in range(n): # 如果当前元素大于 0后面的元素都大于 0不可能和为 0 if nums[i] 0: return result # 跳过重复的元素 if i 0 and nums[i] nums[i-1]: continue # 双指针 left i 1 right n - 1 while left right: total nums[i] nums[left] nums[right] if total 0: # 添加到结果中 result.append([nums[i], nums[left], nums[right]]) # 跳过重复的元素 while left right and nums[left] nums[left1]: left 1 while left right and nums[right] nums[right-1]: right - 1 # 移动指针 left 1 right - 1 elif total 0: # 和小于 0左指针右移 left 1 else: # 和大于 0右指针左移 right - 1 return result测试用例测试用例 1输入nums [-1,0,1,2,-1,-4]输出[[-1,-1,2],[-1,0,1]]测试用例 2输入nums []输出[]测试用例 3输入nums [0]输出[]测试用例 4输入nums [0,0,0]输出[[0,0,0]]总结本题是双指针的经典应用问题主要考察对排序和双指针技巧的理解和使用。通过排序和双指针我们可以有效地找到所有和为 0 的三元组并避免重复。排序的核心思想是将数组按照升序排列这样我们可以使用双指针来高效地查找和为 0 的三元组。双指针的核心思想是通过移动左指针和右指针我们可以根据当前和的大小来调整指针的位置从而找到所有可能的组合。这种方法不仅适用于三数之和问题还可以应用于许多其他需要查找多个元素组合的问题例如四数之和、最接近的三数之和等。掌握排序和双指针的使用对于解决这类问题非常重要。