题目

思路

一句话：固定一个数，把「三数之和」降维成「有序数组中的两数之和」，再用双指针一次线性扫完。

最直白的做法是三重循环枚举 i、j、k，找到和为 0 的存下来，最后去重。它有两个问题：一是 O(n³)，当 n=3000 时约 2.7×10¹⁰ 次，跑不动；二是去重要靠集合保存「已经出现过的三元组」，麻烦且占空间。

稍微改进：枚举一个 i 之后，剩下的问题是找 nums[j] + nums[k] == -nums[i]。但若数组无序，找两数之和还得靠哈希，而三元组整体去重依旧绕不开。

关键观察是先排序。排序带来两件好事：

• 去重变简单：相等的数会挤在一起，跳过相邻的相等值即可，不需要额外集合。
• 双指针可行：对升序数组，左指针 j 右移只会让和变大，右指针 k 左移只会让和变小。于是和偏小就 j++、偏大就 k--，两个指针一路向中间靠拢，每次内层至多走 O(n) 步。

最终复杂度：排序 O(n log n)，加枚举 i 的 O(n) 次内层双指针 O(n)，整体 O(n²)。

解法

1. 把 nums 升序排序。
2. 枚举第一个数 i（到 n-3 即可，要给 j、k 留两个位置）。
3. 如果 nums[i] > 0，直接结束：排序后最小的数都为正，后面不可能凑出 0。
4. 如果 i > 0 且 nums[i] == nums[i-1]，跳过，避免第一个数重复。
5. 令 j = i+1、k = n-1，在 j < k 内双指针：
   • 和小于 0 → j++（要更大的数）；
   • 和大于 0 → k--（要更小的数）；
   • 和等于 0 → 记录 [nums[i], nums[j], nums[k]]，然后同时跳过 j 侧和 k 侧的重复值，再各自向中间收一步。
6. 返回所有记录。

以排序后的 [-3,0,0,0,1,2] 为例走一遍：

接着 i 移到下标 2、3（值都是 0），与上一个值重复，被跳过；下标 4 的值是 1，已经大于 0，直接结束。最终得到 [[-3,1,2],[0,0,0]]。

下图把上面 8 个步骤串成流程，并逐步演示：

C++

class Solution {
public:
 vector<vector<int>> threeSum(vector<int>& nums) {
 int n = nums.size();
 vector<vector<int>> res;
 sort(nums.begin(), nums.end());          // 排序：方便双指针 + 去重  for (int i = 0; i < n - 2; ++i) {
 if (nums[i] > 0) break;              // 最小数都为正，后面不可能凑 0
 if (i > 0 && nums[i] == nums[i - 1]) continue;   // 第一个数去重  int j = i + 1, k = n - 1;
 while (j < k) {
 int sum = nums[i] + nums[j] + nums[k];
 if (sum < 0) {
 ++j;
 } else if (sum > 0) {
 --k;
 } else {
 res.push_back({nums[i], nums[j], nums[k]});
 while (j < k
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。