15. 三数之和
type
status
date
slug
summary
tags
category
difficulty
icon
password
15. 三数之和
给你一个整数数组
nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。
示例 1：
示例 2：
示例 3：
提示：
3 <= nums.length <= 3000
105 <= nums[i] <= 105
解题思路：
- 首先对数组进行排序，这样可以方便去重和使用双指针
- 使用三重循环，其中：
- 第一重循环i遍历数组，作为第一个数
- 第二重循环j从i+1开始，作为第二个数
- 第三重循环k从数组末尾开始，作为第三个数
- 去重处理：
- 对第一个数nums[i]，跳过重复值
- 对第二个数nums[j]，跳过重复值
- 优化：当k向左移动时，如果nums[i] + nums[j] + nums[k-1] >= 0，说明k还可以继续左移
- 当找到nums[i] + nums[j] + nums[k] == 0时，将这三个数加入结果集
时间复杂度分析：
- 排序时间：O(nlogn)
- 双指针遍历时间：O(n²)
- 总时间复杂度：O(n²)
空间复杂度：O(1)，除了存储答案的空间外，只需要常数级的额外空间
- 作者:Episkey
- 链接:https://episkey.top/article/3sum
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
