【算法面试必刷】15. 三数之和

目录

题目

题目链接

思路

复杂度

1. 排序阶段

2. 双指针搜索阶段

3. 总时间复杂度

4. 空间复杂度

代码

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

题目链接

15. 三数之和 - 力扣（LeetCode）https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked

思路

核心思想：排序 + 双指针

为什么需要排序？

1. 有序数组才能使用双指针
2. 方便去重
3. 可以提前终止搜索

为什么用双指针？
将 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; } };