yicong@algo: ~/code/02-two-pointers/0015-3sum.cpp

yicong@algo:~/code/02-two-pointers$ cat 0015-3sum.cpp

15. 三数之和

中等 双指针 题目 ↗ 源码 ↗

// 思路

排序后固定第一个数 nums[x],在它右侧用左右指针找两数之和为 -nums[x]: sum < 0 说明 left 太小,left++;sum > 0 说明 right 太大,right--; 命中后同时移动两个指针并跳过重复值。外层跳过重复的 x,保证三元组不重复。 剪枝:nums[x] > 0 时后面不可能再凑出 0,直接结束; nums[x] 加最大的两个数仍 < 0 时,当前 x 无解,跳过内层。

// 时间复杂度

O(n^2),排序 O(n log n),外层 n 次、每次双指针 O(n)

// 空间复杂度

O(log n)(排序递归栈,不计返回结果;答案本身最坏 O(n^2))

// 易错点

1) 去重要和「身后已处理的位置」比:x 比 x-1、left 比 left-1、right 比 right+1; 和身前比会漏解,例如 [-1,-1,2] 的 x、[-2,1,1] 的 left/right 2) left 的去重要带 left > x+1,否则会把 nums[x] 误当成前一个 left 3) x > 0 防 nums[x-1] 越界,right < n-1 防 nums[right+1] 越界

// 面试口述要点

排序提供单调性,固定最小数后两数之和用双指针 O(n) 解决, 整体从 O(n^3) 降到 O(n^2);若题目要求原下标则不能排序(见 1. 两数之和)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int n = (int)nums.size();

        for (int x = 0; x < n - 2; ++x) {
            if (nums[x] > 0) break;                        // 最小的数已为正,后面不可能凑出 0
            if (x > 0 && nums[x] == nums[x - 1]) continue; // 固定数去重

            // 当前 x 加上最大的两个数仍小于 0,内层双指针不可能有解
            if (nums[x] + nums[n - 2] + nums[n - 1] < 0) continue;

            int left = x + 1;
            int right = n - 1;

            while (left < right) {
                if (left > x + 1 && nums[left] == nums[left - 1]) {
                    ++left;
                    continue;
                }
                if (right < n - 1 && nums[right] == nums[right + 1]) {
                    --right;
                    continue;
                }

                int sum = nums[x] + nums[left] + nums[right];
                if (sum < 0) {
                    ++left;
                } else if (sum > 0) {
                    --right;
                } else {
                    ans.push_back({nums[x], nums[left], nums[right]});
                    ++left;
                    --right;
                }
            }
        }
        return ans;
    }
};

// 本地测试:输入 n,然后 n 个整数;每行输出一个三元组
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<int> nums(n);
    for (int& x : nums) cin >> x;

    vector<vector<int>> ans = Solution().threeSum(nums);
    for (auto& t : ans) cout << t[0] << ' ' << t[1] << ' ' << t[2] << '\n';
    return 0;
}