你好！我是你的OI竞赛教练。很高兴看到你在练习经典题目。LeetCode15 "3Sum"（三数之和）是一道非常经典的双指针与去重逻辑的训练题。

---

第一部分：题目重述

题目名称： 寻找零和三元组 (Find Zero-Sum Triplets) 输入文件： threesum.in 输出文件： threesum.out 时间限制： 1.0 s 内存限制： 256 MB

【题目描述】

给定一个包含 $n$ 个整数的数组 $A$。请你判断是否存在三个元素 $A[i], A[j], A[k]$，满足 $i \neq j$、$i \neq k$ 且 $j \neq k$，使得 $A[i] + A[j] + A[k] = 0$。

请找出所有满足条件且不重复的三元组。

注意：

1. 答案中不可以包含重复的三元组。例如，如果 [-1, 0, 1] 是一个解，那么 [0, -1, 1] 视为同一个解，只输出一次。
2. 输出的三元组内部元素及三元组之间建议按非递减顺序输出（为了判题方便，通常竞赛中会有字典序要求）。

【输入格式】

第一行包含一个整数 $n$，表示数组的大小。 第二行包含 $n$ 个整数，表示数组 $A$ 的元素，整数之间用空格分隔。

【输出格式】

输出若干行，每行包含三个整数，表示一个满足条件的三元组。 要求：每个三元组内部元素从小到大排序；不同三元组之间按照第一个元素、第二个元素、第三个元素的字典序从小到大排序。 如果没有满足条件的三元组，则不输出任何内容。

【样例 1】

输入：

6
-1 0 1 2 -1 -4

输出：

-1 -1 2
-1 0 1

【样例 2】

输入：

3
0 1 1

输出：

(空)

【样例 3】

输入：

3
0 0 0

输出：

0 0 0

【数据范围与提示】

对于 $100\%$ 的数据，满足 $0 \le n \le 3000$，数组元素的值在 $[-10^5, 10^5]$ 范围内，保证结果总数在合理范围内，不会爆输出。

---

第二部分：预备知识点总结

在解决这道题之前，你需要掌握以下“武器”：

1. 排序 (Sorting)：
   • 这是处理去重和双指针的前提。使用 std::sort，时间复杂度 $O(N \log N)$。
2. 双指针法 (Two Pointers)：
   • 在一个有序数组中，寻找两个数之和等于特定值（2Sum问题）的高效方法。
3. 去重逻辑 (Deduplication)：
   • 如何跳过相同的元素以避免产生重复的结果，这是本题的易错点（边界条件）。
4. 复杂度分析：
   • 理解为什么 $O(N^3)$ 会超时，而 $O(N^2)$ 是可接受的。

---

第三部分：读题关键词与审题技巧

在阅读此类题目时，圈出以下关键词：

1. “$i \neq j \neq k$” $\Rightarrow$ 必须是数组中不同位置的三个数。
2. “不重复的三元组” $\Rightarrow$ 核心难点。这意味着 {-1, 0, 1} 和 {-1, 0, 1}（来自不同下标但数值相同）只能算一个。
3. “$n \le 3000$” $\Rightarrow$ 这是暗示时间复杂度的重要线索。
   • $N=3000$，如果算法是 $O(N^3)$，运算量约为 $2.7 \times 10^{10}$，远超 $10^8$ 的限制，必然 TLE (Time Limit Exceeded)。
   • 如果算法是 $O(N^2)$，运算量约为 $9 \times 10^6$，完全可以在 1秒内跑完。

---

第四部分：启发式教学与草稿纸推演

现在，拿出一张草稿纸，我们一步步来推导。

1. 朴素思路（暴力法）

学生思考： 我可以用三层 for 循环，枚举 $i, j, k$，判断 A[i] + A[j] + A[k] == 0。 教练引导： 没错，这是最直观的。但是我们刚才分析了复杂度是 $O(N^3)$，会超时。而且，你怎么处理重复呢？比如 [-1, -1, 0, 1]，你可能会找到两次 (-1, 0, 1)。用 std::set 去重会增加额外的常数开销。我们需要更聪明的方法。

2. 降维打击（化繁为简）

教练引导： $a + b + c = 0$ 这个公式里有三个变量。如果我们固定其中一个数 $a$（假设它在下标 $i$），问题变成了什么？ 学生思考： 变成了在剩下的数里找 $b + c = -a$。 教练总结： 对！这就把 3Sum 问题降级为了 2Sum 问题。我们需要遍历 $i$（$O(N)$），然后在剩下的区间里做一次 2Sum。

3. 有序化带来的红利

教练引导： 在无序数组里找 $b+c = \text{target}$ 比较麻烦。如果数组是有序的，比如： [-4, -1, -1, 0, 1, 2] 我们固定第一个数 -4，目标是在后面找和为 4 的两个数。 我们用两个指针，一个指头 $L$，一个指尾 $R$。

• 如果 $A[L] + A[R] < \text{target}$，说明和太小了，怎么办？（$L$ 往右移，让和变大）
• 如果 $A[L] + A[R] > \text{target}$，说明和太大了，怎么办？（$R$ 往左移，让和变小）

4. 草稿纸演练（处理去重）

场景： 数组排序后为 [-1, -1, -1, 0, 1, 2]。 我们来画图模拟：

• 第 1 轮： 固定 $i=0$，即 $A[i] = -1$。目标找 $b+c = 1$。

  • 区间是 [-1, -1, 0, 1, 2] (下标 1 到 5)
  • $L$ 指向下标 1 ($val=-1$)， $R$ 指向下标 5 ($val=2$)。
  • $-1 + 2 = 1$。Bingo! 找到一组 (-1, -1, 2)。
  • 关键点来了： 找到答案后，$L$ 和 $R$ 都要移动。如果 $L$ 移动到下标 2，值还是 $-1$，会怎么样？
  • 学生： 会再次找到 (-1, 2)，组成 (-1, -1, 2)，重复了！
  • 教练： 所以，当指针移动时，如果数值和刚才一样，必须跳过！

• 第 2 轮： $i$ 移动到下标 1。$A[i]$ 还是 $-1$。

  • 如果我们继续做，会找到 (-1, 0, 1)。
  • 等等，这和第 1 轮有没有重叠的风险？或者说，对于 $i$，如果 $A[i] == A[i-1]$，我们要不要做？
  • 学生： 第一个 $-1$ 做完后，已经把包含 $-1$ 的所有组合找完了。第二个 $-1$ 再做，肯定会找到重复的（因为它是第一个的子集）。
  • 教练： 非常好！所以外层循环 $i$ 也要去重。

5. 伪代码逻辑构建

1. 排序数组 A
2. 遍历 i 从 0 到 n-3:
    3. 如果 i > 0 且 A[i] == A[i-1]，跳过 (continue) // 外层去重
    4. 设 L = i + 1, R = n - 1
    5. 当 L < R 时:
        sum = A[i] + A[L] + A[R]
        如果 sum == 0:
            记录答案 (A[i], A[L], A[R])
            L++, R--
            // 内层去重
            while L < R 且 A[L] == A[L-1]: L++ 
            while L < R 且 A[R] == A[R+1]: R--
        如果 sum < 0:
            L++
        如果 sum > 0:
            R--

---

第五部分：NOI 风格 C++14 参考代码

这是可以直接在竞赛环境中提交的完整代码（包含IO优化和完整的 main 函数）。

/**
 * NOI Style Solution for 3Sum
 * Language: C++14
 * Time Complexity: O(N^2)
 * Space Complexity: O(1) (excluding output storage)
 */
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义最大数据量，方便查阅，虽vector动态开点，但心中要有数
const int MAXN = 3005;

void solve() {
    int n;
    if (!(cin >> n)) return; // 处理输入结束
    
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    // 1. 排序：这是双指针和去重的基础
    sort(nums.begin(), nums.end());

    // 结果集
    vector<vector<int>> ans;

    // 2. 固定第一个数 nums[i]
    for (int i = 0; i < n - 2; ++i) {
        // 剪枝：如果当前最小的数都大于0，后面不可能凑出0了
        if (nums[i] > 0) break;

        // 外层去重：如果当前数与上一个数相同，跳过
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int target = -nums[i];
        int left = i + 1;
        int right = n - 1;

        // 3. 双指针寻找剩下的两个数
        while (left < right) {
            int sum = nums[left] + nums[right];

            if (sum == target) {
                // 找到一组解
                ans.push_back({nums[i], nums[left], nums[right]});
                
                // 移动指针
                left++;
                right--;

                // 内层去重：跳过左边重复的数
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                // 内层去重：跳过右边重复的数
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
            } 
            else if (sum < target) {
                // 和太小，左指针右移
                left++;
            } 
            else { // sum > target
                // 和太大，右指针左移
                right--;
            }
        }
    }

    // 4. 按格式输出
    // 题目并未要求输出的顺序，但通常OJ判题如果不使用Special Judge，
    // 需要按照字典序输出。我们在收集时已经是i从小到大，且L从小到大，
    // 所以ans本身就是有序的。
    for (const auto& triplet : ans) {
        cout << triplet[0] << " " << triplet[1] << " " << triplet[2] << "\n";
    }
}

int main() {
    // 竞赛常用 IO 优化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

第六部分：教练点评与思维拓展

1. 关于 nums[i] > 0 的剪枝：
   • 这是一个小的优化点。因为数组已经排序，如果 nums[i] > 0，那么其后的 nums[L] 和 nums[R] 肯定也大于 0，三者之和不可能为 0。这个判断在全正数数据下能大幅提升速度。
2. 边界条件：
   • 注意 $i < n-2$，因为至少要留两个位置给 $L$ 和 $R$。
   • 注意去重时的 left < right 保护，防止数组越界。
3. 时间复杂度：
   • 排序：$O(N \log N)$
   • 双指针遍历：外层循环 $N$ 次，内层双指针最多遍历 $N$ 次，总体 $O(N^2)$。
   • 对于 $N=3000$，操作数约 $9 \times 10^6$，非常稳。
4. 空间复杂度：
   • 除了存储答案的空间，只用了常数个变量，空间复杂度 $O(\log N)$（排序栈空间）或 $O(1)$。

同学们，这道题的精髓在于 “有序化” 和 “不重不漏”。下去后请尝试不看代码，自己在草稿纸上写出完整的逻辑，并思考如果题目改成“三数之和最接近 $K$”该怎么做？逻辑是一样的！