题意概括

给定一个包含 $n$ 个整数的数组 nums，我们需要找到所有满足 $a+b+c=0$ 且互不重复的三元组 $[a, b, c]$。

数据范围:

• $3 \le n \le 3000$
• $-10^5 \le nums[i] \le 10^5$

基础知识

本题的核心解法是排序 + 双指针。

1. 排序: 首先对整个数组进行升序排序。排序的好处有两个：

   • 可以方便地跳过重复的元素，从而避免产生重复的三元组结果。
   • 可以利用数组的单调性，使用双指针从两端向中间移动，以线性时间复杂度找到符合条件的元素对。

2. 双指针: 排序后，我们遍历数组，用变量 $i$ 固定第一个元素 a[i]。然后，我们设定两个指针，$l$ 指向 $i+1$（左端），$r$ 指向数组末尾 $n-1$（右端）。

   • 计算三个数的和 $sum = a[i] + a[l] + a[r]$。
   • 如果 $sum < 0$，说明和太小了，需要增大，因此我们将左指针 $l$ 右移一位。
   • 如果 $sum > 0$，说明和太大了，需要减小，因此我们将右指针 $r$ 左移一位。
   • 如果 $sum = 0$，我们找到了一个满足条件的三元组。将其存入结果中。为了避免重复，我们需要将 $l$ 和 $r$ 移动到下一个不同的元素上。

通过固定一个数，将三数之和问题转化为两数之和问题，总的时间复杂度为排序的 $O(N \log N)$ 加上遍历和双指针的 $O(N^2)$，所以最终时间复杂度为 $O(N^2)$。空间复杂度为 $O(1)$（不考虑存储结果的空间）。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    sort(a.begin(), a.end()); // 排序是双指针算法的前提

    vector<vector<int>> ans;

    for (int i = 0; i < n; ++i) {
        // 避免对第一个元素重复处理
        if (i > 0 && a[i] == a[i - 1]) {
            continue;
        }

        int l = i + 1;
        int r = n - 1;

        while (l < r) {
            int sum = a[i] + a[l] + a[r];

            if (sum < 0) {
                l++;
            } else if (sum > 0) {
                r--;
            } else {
                ans.push_back({a[i], a[l], a[r]});

                // 跳过重复的第二个数
                while (l < r && a[l] == a[l + 1]) {
                    l++;
                }
                // 跳过重复的第三个数
                while (l < r && a[r] == a[r - 1]) {
                    r--;
                }

                // 移动指针寻找新的组合
                l++;
                r--;
            }
        }
    }

    for (const auto& v : ans) {
        cout << v[0] << " " << v[1] << " " << v[2] << "\n";
    }

    return 0;
}

/*
样例 1:
输入:
6
-1 0 1 2 -1 -4
输出:
-1 -1 2
-1 0 1

样例 2:
输入:
5
0 0 0 0 0
输出:
0 0 0
*/