15. 三数之和

难度：🟡 Medium | 标签：双指针、数组、排序 | 状态：⬜ LeetCode 链接

思路

排序后固定一个数 nums[i]，剩下用双指针在 [i+1, n-1] 找两数之和等于 -nums[i]。

去重：

• 外层：if (i > 0 && nums[i] == nums[i-1]) continue;
• 内层：找到一个三元组后，l 和 r 都跳过相同值

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        int n = nums.size();
        for (int i = 0; i + 2 < n; ++i) {
            if (nums[i] > 0) break;                          // 剪枝
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = n - 1, t = -nums[i];
            while (l < r) {
                int s = nums[l] + nums[r];
                if (s == t) {
                    res.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;
                } else if (s < t) ++l;
                else --r;
            }
        }
        return res;
    }
};

复杂度

• 时间 O(n²)，空间 O(log n)（排序栈）

易错 / 回顾

• 三处去重：外层 i、内层 l、内层 r
• 剪枝 nums[i] > 0 提前结束（排序后后面都更大）
• 不能用哈希——会重复且不好去重