你好！我是你的OI金牌教练。LeetCode 18题（4Sum）是一道非常经典的双指针与去重逻辑训练题。在NOI体系中，它属于基础算法-枚举与模拟或线性表的范畴，但对代码细节的掌控能力要求较高。

---

四数之和 (Four Sum)

【题目描述】 给定一个包含 $n$ 个整数的序列 $A$ ($A_1, A_2, \dots, A_n$) 和一个目标值 $target$。 请你从序列中找出满足 $a, b, c, d$ 四个下标互不相同（$1 \le a < b < c < d \le n$），且 $A_a + A_b + A_c + A_d = target$ 的所有四元组 $(A_a, A_b, A_c, A_d)$。

你需要按照字典序输出所有满足条件的不重复四元组。 注：两个四元组被认为重复，当且仅当它们包含的四个数值完全相同（不考虑顺序）。例如 [1, 0, -1, 0] 和 [0, -1, 1, 0] 是重复的。

【输入格式】 第一行包含两个整数 $n$ 和 $target$，分别表示序列长度和目标和。 第二行包含 $n$ 个整数，表示序列 $A$ 的元素，整数之间用空格分隔。

【输出格式】 输出若干行，每行包含四个整数，表示一个满足条件的四元组。 要求：

1. 每个四元组内部的元素必须按非降序排列。
2. 输出的四元组之间，按照第一个元素大小升序排列；若第一个元素相同，按第二个元素升序，依此类推（即字典序）。
3. 若无解，则不输出任何内容。

【样例输入 1】

6 0
1 0 -1 0 -2 2

【样例输出 1】

-2 -1 1 2
-2 0 0 2
-1 0 0 1

【样例输入 2】

5 3
2 2 2 2 2

【样例输出 2】

(说明：没有四个数的和能等于3)

【数据范围与提示】

• 对于 $100\%$ 的数据，满足 $1 \le n \le 200$。
• $-10^9 \le A_i \le 10^9$。
• $-10^9 \le target \le 10^9$。
• 注意：计算四个整数之和时可能会超过 32 位有符号整数的范围。

---

第一部分：审题关键词与陷阱

在读题时，你的目光应该像扫描仪一样捕捉以下关键词，并在草稿纸上圈出来：

1. “不重复” (Unique/Distinct)：这是本题的灵魂。题目要求四元组集合不能重复，且四元组内部的索引不能相同。这意味着我们需要处理两种去重：
   • 选取的元素去重：如果数组里有两个2，我们不能把它们视为完全一样的数字处理多次，导致结果集里出现两个[2, 2, 3, 4]。
   • 结果集去重：输出的四元组顺序无关，但内容不能完全一致。
2. “$N$ 的范围” ($1 \le N \le 200$)：
   • 这暗示了时间复杂度可以是 $O(N^3)$。因为 $200^3 = 8 \times 10^6$，在计算机1秒处理 $10^8$ 次运算的通常标准下，是绝对安全的。
   • 如果是 $N=1000$，我们可能需要 $O(N^2 \log N)$ 或 $O(N^2)$ 的解法，但 $N=200$ 给了我们暴力优化（多层循环+双指针）的空间。
3. 数据范围 ($-10^9 \le nums[i] \le 10^9$)：
   • 警报：四个 $10^9$ 相加是 $4 \times 10^9$，超过了 int (约 $2.1 \times 10^9$) 的上限。在计算和时必须使用 long long。

---

第二部分：预备知识点

在解决这道题之前，你需要熟练掌握：

1. 排序 (Sorting)：这是去重和使用双指针的前提。
2. 双指针法 (Two Pointers)：左右指针向中间逼近的技巧，通常用于将 $O(N^2)$ 的暴力搜索降维到 $O(N)$。
3. 整数溢出处理：C++中 long long 的使用。
4. 循环控制：continue 和 break 的灵活运用（用于剪枝）。

---

第三部分：启发式教学——草稿纸上的推演

假设我们在黑板前，现在数组是乱序的：[1, 0, -1, 0, -2, 2]，目标 target = 0。

1. 降维打击思路

• 思考：如果是求两数之和（2Sum），怎么做？
  • 学生：排序后，用头尾指针 L 和 R。如果 sum < target，L++；如果 sum > target，R--。
• 思考：如果是三数之和（3Sum），怎么做？
  • 学生：固定第一个数 nums[i]，剩下的变成在 [i+1, n-1] 区间里找 2Sum。
• 推论：那四数之和（4Sum）呢？
  • 学生：固定第一个数 nums[i]，再固定第二个数 nums[j]，剩下的在 [j+1, n-1] 里找 2Sum！

2. 草稿纸演练（核心：去重与剪枝）

画出排序后的数组：[-2, -1, 0, 0, 1, 2]

第一层循环 (i)：固定 nums[i]。

• i=0, nums[i] = -2。

第二层循环 (j)：固定 nums[j] (从 i+1 开始)。

• j=1, nums[j] = -1。
• 现在我们要找两个数，和为 0 - (-2) - (-1) = 3。
• 左指针 L = j+1 (指向 0)，右指针 R = n-1 (指向 2)。
• 0 + 2 = 2 < 3，L右移。
• ...找到解...

关键点来了：如何处理重复？ 假设数组变成了 [-2, -2, 0, 0, 1, 2]。

• 当 i=0 处理完 nums[0]=-2 后，i 变成 1，nums[1] 还是 -2。
• 提问：如果再次以 nums[1] 为起点计算，会不会产生重复的结果？
• 结论：绝对会。因为 nums[0] 开头的情况已经覆盖了 nums[1] 能组合的所有情况。
• 代码动作：if (i > 0 && nums[i] == nums[i-1]) continue;

金牌选手的优化（剪枝 Pruning）： 在 $O(N^3)$ 算法中，常数优化非常重要。

1. 最小性剪枝：如果 nums[i] 加上后面最小的三个数 > target，那后面无论怎么选都大了，直接 break。
2. 最大性剪枝：如果 nums[i] 加上数组最大的三个数 < target，那这个 nums[i] 太小了，怎么加都不够，直接 continue 看下一个更大的 nums[i]。

3. 复杂度分析

• 时间复杂度：排序 $O(N \log N)$。两层循环 $O(N^2)$，内部双指针 $O(N)$。总复杂度 $O(N^3)$。对于 $N=200$，运算量约为 $8 \times 10^6$，非常稳。
• 空间复杂度：$O(\log N)$ (排序栈空间) 或 $O(1)$ (取决于排序实现)，不计算存储答案的空间。

---

NOI 风格参考代码 (C++14)

/**
 * Title: Four Sum
 * Standard: C++14
 * Complexity: O(N^3) Time, O(1) Extra Space (excluding output)
 * Author: OI Coach
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 优化 I/O 操作
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long target; // 使用 long long 防止 target 本身就在边界
    if (!(cin >> n >> target)) return 0;

    vector<long long> nums(n); // 使用 long long 防止加法溢出
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

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

    vector<vector<long long>> ans;

    // 如果元素不足4个，直接结束
    if (n < 4) {
        return 0;
    }

    // 第一层循环
    for (int i = 0; i < n - 3; ++i) {
        // 去重：如果当前数字和上一个数字相同，跳过
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        // 剪枝 1 (Min check)：如果当前最小的四个数之和都大于 target，后面不可能有解
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;

        // 剪枝 2 (Max check)：如果当前数加上最大的三个数之和还小于 target，当前数太小，找下一个
        if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;

        // 第二层循环
        for (int j = i + 1; j < n - 2; ++j) {
            // 去重：注意这里是 j > i + 1
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;

            // 二级剪枝
            if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
            if (nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;

            // 双指针
            int left = j + 1;
            int right = n - 1;

            while (left < right) {
                long long sum = nums[i] + nums[j] + nums[left] + nums[right];

                if (sum == target) {
                    // 找到答案
                    // NOI题目通常要求直接输出，或存入容器
                    cout << nums[i] << " " << nums[j] << " " << nums[left] << " " << nums[right] << "\n";

                    // 指针移动并去重
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    
                    left++;
                    right--;
                } 
                else if (sum < target) {
                    left++;
                } 
                else {
                    right--;
                }
            }
        }
    }

    return 0;
}

希望这个拆解能帮你在脑海中建立起解决此类“K数之和”问题的通用模型！在练习时，记得多问自己一句：“这里的重复情况我考虑全了吗？” 加油！