【算法面试必刷】15. 三数之和
目录
题目
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
题目链接
思路
核心思想：排序 + 双指针
为什么需要排序？
- 有序数组才能使用双指针
- 方便去重
- 可以提前终止搜索
为什么用双指针？
将 O(n³) 的暴力搜索优化为 O(n²)
复杂度
1. 排序阶段
- 使用快速排序或归并排序
- 时间复杂度：O(n log n)
2. 双指针搜索阶段
外层循环：执行 n-2 次，O(n) 内层循环：双指针，最坏 O(n) 总计：O(n × n) = O(n²)
为什么是 O(n²)？
- 固定
nums[i]，在[i+1, n-1]区间用双指针找两个数 - 双指针遍历区间长度平均为 n/2
- 所以是：
n × (n/2) ≈ O(n²)
3. 总时间复杂度
text
O(n log n) + O(n²) = O(n²)
因为 n² 的增长速度比 n log n 快，所以主导项是 O(n²)。
4. 空间复杂度
排序：O(log n) 到 O(n)（取决于排序算法） 结果存储：O(k)，k是结果数量 额外空间：O(1)（双指针只用常数空间） 总空间复杂度：O(n)（如果考虑结果存储） 如果不考虑结果存储：O(log n) 或 O(1)
代码
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ans; // 存储结果 int n = nums.size(); // 数组长度 // 1. 特殊情况处理：数组长度正好为3 if (n == 3) { int sum = nums[0] + nums[1] + nums[2]; if (sum == 0) { ans.push_back({nums[0], nums[1], nums[2]}); } return ans; // 直接返回，不需要复杂处理 } // 2. 关键步骤：排序（使双指针法可行） sort(nums.begin(), nums.end()); // 3. 遍历每个数字作为第一个数 for (int i = 0; i < n; i++) { // 3.1 去重：跳过重复的第一个数 // 因为排序后，相同的数字会相邻 if (i != 0 && nums[i - 1] == nums[i]) { continue; } // 3.2 双指针初始化 int l = i + 1; // 左指针，从i后面开始 int r = n - 1; // 右指针，从末尾开始 // 3.3 双指针查找剩余两个数 while (l < r) { int sum = nums[i] + nums[l] + nums[r]; if (sum > 0) { // 和太大，需要减小，右指针左移 r--; } else if (sum < 0) { // 和太小，需要增大，左指针右移 l++; } else { // 找到和为0的三元组 ans.push_back({nums[i], nums[l], nums[r]}); // 去重：跳过重复的左指针元素 while (l < r && nums[l] == nums[l + 1]) { l++; } // 去重：跳过重复的右指针元素 while (l < r && nums[r] == nums[r - 1]) { r--; } // 移动指针，继续查找其他可能 l++; r--; } } } return ans; } };