Two Sum 与 K-Sum 变种体系¶

两数之和（Two Sum） 是每一位算法学习者迈入算法大门的第一课。然而，由其衍生出的算法体系极其庞大深厚：从哈希空间换时间、有序对撞双指针，到三数之和（3-Sum）的三重去重技巧、四数之和（4-Sum）的极致极限制剪枝、通用 \(K\)-Sum 递归降维，再到分组折半搜索（Meet-in-the-Middle）以及差值、前缀和、同余、异或等代数变换，构成了一整套极其经典的算法知识图谱。

1. Two Sum 基础范式与时空权衡¶

对于无序数组与有序数组，Two Sum 展现出两种截然不同的经典时空权衡解法。

1.1 无序数组：一次遍历哈希法 (\(\mathcal{O}(N)\) 时间, \(\mathcal{O}(N)\) 空间)¶

核心思路是“边查边存（One-Pass Hash）”：

遍历到当前元素 \(x\) 时，我们需要寻找的目标配对值是 \(target - x\)；
我们先在哈希表中查询 \(target - x\) 是否已经存在：
若存在，直接返回其保存的历史下标与当前下标；
若不存在，将当前元素及其下标存入哈希表：table[x] = i。

核心细节： “边查边存”比“先全部存入哈希表再查”更优雅：它天然避免了元素自身与自身配对（自引用）的 Bug，例如当 \(nums = [3, 2, 4], target = 6\) 时，若直接全量存哈希表，查询 \(6 - 3 = 3\) 会错误匹配到自己。

#include <vector>
#include <unordered_map>

std::vector<int> two_sum_hash(const std::vector<int> &nums, int target) {
    std::unordered_map<int, int> seen;
    for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
        int complement = target - nums[i];
        if (seen.find(complement) != seen.end()) {
            return {seen[complement], i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

1.2 有序数组：双向对撞双指针法 (\(\mathcal{O}(N)\) 时间, \(\mathcal{O}(1)\) 空间)¶

若数组已经按升序排序（如 LeetCode 167），则无需浪费额外内存，可利用单调性采用对撞双指针：

左指针 \(l\) 指向首位，右指针 \(r\) 指向末位；
计算当前和 \(sum = nums[l] + nums[r]\)：
若 \(sum == target\)：找到答案；
若 \(sum < target\)：因为数组升序，右侧的数无法再变大，唯一让和增大的方式是将左指针右移（\(l++\)）；
若 \(sum > target\)：唯一让和减小的方式是将右指针左移（\(r--\)）。
每次比较必定排除一个无效的指针位置，至多 \(N\) 步即可收敛。

#include <vector>

std::vector<int> two_sum_sorted(const std::vector<int> &nums, int target) {
    int l = 0, r = static_cast<int>(nums.size()) - 1;
    while (l < r) {
        long long sum = static_cast<long long>(nums[l]) + nums[r];
        if (sum == target) return {l, r};
        else if (sum < target) l++;
        else r--;
    }
    return {};
}

1.3 特殊数据结构上的 2-Sum 变种¶

二叉搜索树上的 2-Sum (LeetCode 653)：
面对给定的 BST，除了用哈希表或先中序遍历导出数组外，还可以维护正向与反向两个 BST 迭代器（双栈模拟中序与逆中序遍历）；
两个迭代器分别从最小值和最大值向中间逼近，实现严格 \(\mathcal{O}(N)\) 时间与 \(\mathcal{O}(\text{树高})\) 辅助空间的对撞双指针。
动态数据流设计 (Two Sum III / LeetCode 170)：
维护一个频次哈希表 count；
add(number)：count[number]++，耗时 \(\mathcal{O}(1)\)；
find(value)：遍历哈希表中的键 \(x\)，查询 \(y = value - x\) 是否存在；特别地，若 \(x == y\)，要求 count[x] >= 2。单次查询 \(\mathcal{O}(U)\)（\(U\) 为不同数值个数）。

2. 从 2-Sum 到 K-Sum 维度延展与剪枝去重¶

当维度从 2 提升到 3、4 乃至任意 \(K\) 时，核心策略是：先排序，然后逐层枚举固定外层变量，将问题递归降维至 2-Sum，最后用对撞双指针收尾。

2.1 3-Sum（三数之和）：三重去重法则 (LeetCode 15)¶

题目要求寻找所有满足 \(nums[i] + nums[j] + nums[k] == 0\) 且不重复的三元组。

三重去重规则：¶

外层基准数去重：
排序后，外层循环遍历 \(i\)；
若当前元素与前一个元素相同，即 i > 0 && nums[i] == nums[i - 1]，直接 continue 跳过。
内层对撞双指针去重：
当找到一组解 \(nums[i] + nums[l] + nums[r] == 0\) 后：
- 左指针向右跳过所有连续重复元素：while (l < r && nums[l] == nums[l + 1]) l++;
- 右指针向左跳过所有连续重复元素：while (l < r && nums[r] == nums[r - 1]) r--;
- 最后左右指针各推进一步：l++; r--;。

#include <vector>
#include <algorithm>

std::vector<std::vector<int>> three_sum(std::vector<int> &nums) {
    std::sort(nums.begin(), nums.end());
    int n = nums.size();
    std::vector<std::vector<int>> res;

    for (int i = 0; i < n - 2; ++i) {
        if (nums[i] > 0) break; // 最小数大于 0，三数和必大于 0，提前终止
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 基准去重

        int l = i + 1, r = n - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum == 0) {
                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 (sum < 0) {
                l++;
            } else {
                r--;
            }
        }
    }
    return res;
}

2.2 3-Sum 经典衍生变体¶

最接近的三数之和 (3-Sum Closest / LeetCode 16)：
排序后对撞双指针，维护全局最小差值 \(|sum - target|\)；若当前 \(sum < target\) 则 \(l++\)；若 \(sum > target\) 则 \(r--\)；若 \(sum == target\) 直接返回。
较小的三数之和 (3-Sum Smaller / LeetCode 259)：
寻找满足 \(nums[i] + nums[j] + nums[k] < target\) 的三元组数量；
区间批量贡献统计技巧：若当前 \(nums[i] + nums[l] + nums[r] < target\)，由于数组有序，此时以 \(nums[l]\) 为第二个数、第三个数取 \(l+1, l+2, \dots, r\) 中的任意一个，三数和都必定小于 \(target\)！因此直接批量累加贡献：

\[ count \leftarrow count + (r - l) \]

然后只需将左指针 \(l++\)，无需逐个枚举！

2.3 4-Sum（四数之和）与极值剪枝 (LeetCode 18)¶

在 4-Sum 中，如果直接写两重循环 + 双指针，在面对构造的极端测试用例时常数较大。必须引入极值极限制裁剪枝（Bounding Pruning）：

对于当前层（例如固定前两个数 \(nums[i], nums[j]\)）：

下界剪枝（最小和超标）：当前能取到的理论最小和为 \(nums[i] + nums[j] + nums[j+1] + nums[j+2]\)。若该最小和已经严格大于 \(target\)，则后续所有组合必然更大，直接 break 终止当前循环！
上界剪枝（最大和不足）：当前能取到的理论最大和为 \(nums[i] + nums[j] + nums[n-2] + nums[n-1]\)。若该最大和依然严格小于 \(target\)，说明当前选择太小了，continue 推进当前层至更大的数。

2.4 通用 K-Sum 递归降维模板¶

无论 \(K\) 为多少，均可通过统一的递归回溯进行降维，当递归至 \(K = 2\) 时调用对撞双指针。

#include <vector>
#include <algorithm>

class KSumSolver {
private:
    std::vector<std::vector<int>> res;

    void k_sum_internal(std::vector<int> &nums, long long target, int start, int k, std::vector<int> &path) {
        int n = nums.size();
        if (start >= n) return;

        // 极值极限制剪枝
        long long min_possible = 0, max_possible = 0;
        for (int i = 0; i < k; ++i) {
            if (start + i < n) min_possible += nums[start + i];
            if (n - 1 - i >= start) max_possible += nums[n - 1 - i];
        }
        if (min_possible > target || max_possible < target) return;

        // 递归基：K = 2 采用双指针收尾
        if (k == 2) {
            int l = start, r = n - 1;
            while (l < r) {
                long long sum = static_cast<long long>(nums[l]) + nums[r];
                if (sum == target) {
                    std::vector<int> combo = path;
                    combo.push_back(nums[l]);
                    combo.push_back(nums[r]);
                    res.push_back(combo);
                    while (l < r && nums[l] == nums[l + 1]) l++;
                    while (l < r && nums[r] == nums[r - 1]) r--;
                    l++; r--;
                } else if (sum < target) {
                    l++;
                } else {
                    r--;
                }
            }
            return;
        }

        // K > 2: 枚举当前基准数并递归进入 (K - 1)-Sum
        for (int i = start; i <= n - k; ++i) {
            if (i > start && nums[i] == nums[i - 1]) continue; // 当前层去重
            path.push_back(nums[i]);
            k_sum_internal(nums, target - nums[i], i + 1, k - 1, path);
            path.pop_back();
        }
    }

public:
    std::vector<std::vector<int>> solve(std::vector<int> nums, long long target, int k) {
        std::sort(nums.begin(), nums.end());
        res.clear();
        std::vector<int> path;
        k_sum_internal(nums, target, 0, k, path);
        return res;
    }
};

3. 分组折半哈希 (Meet-in-the-Middle) 与 4-Sum II¶

3.1 4-Sum II 模型 (LeetCode 454)¶

题目特征：给定四个独立的等长整数数组 \(A, B, C, D\)（大小均为 \(N\)），计算有多少个四元组 \((i, j, k, l)\) 满足：

\[ A[i] + B[j] + C[k] + D[l] = 0 \]

若直接四重循环枚举，复杂度为 \(\mathcal{O}(N^4)\)。由于这四个数组彼此完全独立，无需考虑同一数组内下标不能重复的复杂去重约束。

折半思想（Meet-in-the-middle）：¶

我们将四个数组划分为两半：前半部分 \((A, B)\) 和后半部分 \((C, D)\)：

预处理前半部分：枚举所有 \((A[i], B[j])\) 的组合（共 \(N^2\) 对），将其和的出现频次存入哈希表 count_ab[A[i] + B[j]]++；
查询后半部分：枚举所有 \((C[k], D[l])\) 的组合，在哈希表中累加其相反数存在的频次：

\[ ans \leftarrow ans + \text{count\_ab}[-(C[k] + D[l])] \]
复杂度分析：时间复杂度由 \(\mathcal{O}(N^4)\) 惊人地降至 \(\mathcal{O}(N^2)\)！空间复杂度为 \(\mathcal{O}(N^2)\)。

#include <vector>
#include <unordered_map>

int four_sum_count(const std::vector<int>& nums1, const std::vector<int>& nums2,
                   const std::vector<int>& nums3, const std::vector<int>& nums4) {
    std::unordered_map<int, int> ab_sum;
    for (int a : nums1) {
        for (int b : nums2) {
            ab_sum[a + b]++;
        }
    }

    int count = 0;
    for (int c : nums3) {
        for (int d : nums4) {
            int target = -(c + d);
            auto it = ab_sum.find(target);
            if (it != ab_sum.end()) {
                count += it->second;
            }
        }
    }
    return count;
}

3.2 进阶延展：折半枚举 (Meet-in-the-Middle on Subsets)¶

当面对超大背包或子集和问题时，若集合元素总数 \(N \le 40\)：

暴力枚举所有子集的复杂度为 \(2^{40} \approx 10^{12}\)，超时；
将集合拆分为前 \(N/2 = 20\) 个元素和后 \(N/2 = 20\) 个元素；
分别枚举生成两组子集和（各 \(2^{20} \approx 10^6\) 个数）；
将第二组排序，利用 2-Sum 双指针或二分查找在第一组中配对；
总体时间复杂度压缩为 \(\mathcal{O}(N \cdot 2^{N/2})\)，瞬间秒杀！

4. 代数与前缀变换衍生模型 (Algebraic Variants)¶

Two Sum 的深远影响力在于：许多看似完全无关的连续子序列问题，在经过代数变形后，本质上全是 2-Sum！

4.1 差值 2-Sum (\(A[i] - A[j] = K\))¶

等价变形：\(A[i] = A[j] + K\)。
解法：
若数组有序，采用同向快慢双指针（Sliding Window）：慢指针指向 \(j\)，快指针指向 \(i\)。若差值较小则 \(i++\)，差值过大则 \(j++\)（如 LeetCode 532 寻找 \(k\)-diff 数对）。

4.2 前缀和 2-Sum：和为 K 的连续子数组 (LeetCode 560)¶

要求求解满足 \(\sum_{t=i}^{j} nums[t] = K\) 的连续子数组数量。根据前缀和公式：

\[ \text{sum}(i \dots j) = prefix[j] - prefix[i - 1] = K \iff prefix[i - 1] = prefix[j] - K \]

这恰好就是经典的 2-Sum 模型：当前遍历到前缀和 \(prefix[j]\) 时，我们需要查询此前历史上有多少个位置的前缀和恰好为 \(prefix[j] - K\)；
使用哈希表维护历史前缀和频次，初始化 count[0] = 1，可以在严格 \(\mathcal{O}(N)\) 时间内在线统计完毕。

4.3 同余 2-Sum：余数互补对数 (LeetCode 1010 & 523)¶

整除两数和模型：要求 \((A[i] + A[j]) \equiv 0 \pmod K\)。
数值 \(A[i]\) 的余数为 \(r = A[i] \pmod K\)；
寻找的补数余数应当满足 \(r' = (K - r) \pmod K\)；
维护长度为 \(K\) 的计数数组 cnt[K]，边查边存 ans += cnt[(K - r % K) % K]。
同余前缀和模型：连续子数组和为 \(K\) 的倍数 \(\iff prefix[j] \equiv prefix[i - 1] \pmod K\)。哈希表记录每个余数第一次出现的下标即可。

4.4 位运算 2-Sum：异或对与 0-1 Trie 树¶

等价变形：根据异或的自反性：

\[ A[i] \oplus A[j] = K \iff A[j] = K \oplus A[i] \]

若求是否存在某个固定差值 \(K\) 的数对，直接利用哈希表查询 \(K \oplus A[i]\)；
最大异或对 (Maximum XOR Pair / LeetCode 421)：若求两数异或的最大值（即 \(\max(A[i] \oplus A[j])\)），则将所有元素插入 0-1 字典树（Trie），遍历每个数值，在 Trie 树上从最高二进制位开始贪心下潜与当前位相反的分支，达到 \(\mathcal{O}(N \log C)\) 的极速查询。

5. LeetCode 经典真题精选与题解提示¶

LeetCode 1 - 两数之和 (Two Sum) 简单
提示

哈希法基石。
- 边查边存：遍历每个数 \(x\)，查哈希表中是否有 \(target - x\)。若有即得答案，若无则存入 seen[x] = i。保证 \(\mathcal{O}(N)\) 时间与 \(\mathcal{O}(N)\) 空间，避免自引用。
LeetCode 167 - 两数之和 II - 输入有序数组 (Two Sum II - Input Array Is Sorted) 中等
提示

对撞双指针标杆。
- 数组已有序，利用单调性设立首尾双指针。
- \(sum < target\) 则左指针右移，\(sum > target\) 则右指针左移。严格 \(\mathcal{O}(N)\) 时间与 \(\mathcal{O}(1)\) 空间。
LeetCode 15 - 三数之和 (3Sum) 中等
提示

排序 + 双指针 + 三重去重。
- 排序后固定第一个数 \(nums[i]\)，双指针寻找 \(nums[l] + nums[r] == -nums[i]\)。
- 去重核心：\(nums[i] == nums[i-1]\) 必须 continue；找到答案后双指针利用 while 跳过连续相同元素。时间复杂度 \(\mathcal{O}(N^2)\)。
LeetCode 16 - 最接近的三数之和 (3Sum Closest) 中等
提示

双指针逼近极值。
- 排序后固定基准数，对撞双指针逼近。维护当前三数之和与 \(target\) 差值的绝对值最小值。时间复杂度 \(\mathcal{O}(N^2)\)。
LeetCode 18 - 四数之和 (4Sum) 中等
提示

双重枚举 + 上下界极限制剪枝。
- 外层双循环枚举 \(i, j\)，内层双指针。必须在每层加入极值剪枝（最小和超标 break，最大和不足 continue），防止 TLE；累加时使用 long long 防 32 位溢出。
LeetCode 454 - 四数相加 II (4Sum II) 中等
提示

分组折半哈希 (Meet-in-the-middle)。
- 四个独立数组：两两分组。哈希表记录 \(nums1[i] + nums2[j]\) 的频次（\(\mathcal{O}(N^2)\)），再枚举 \(nums3[k] + nums4[l]\) 在哈希表中累加其相反数的出现次数。总时间复杂度降至 \(\mathcal{O}(N^2)\)。
LeetCode 560 - 和为 K 的子数组 (Subarray Sum Equals K) 中等
提示

前缀和映射 2-Sum。
- 连续子数组和转为前缀和之差：\(prefix[j] - prefix[i-1] = K\)。遍历 \(j\) 时，在哈希表中统计 \(prefix[j] - K\) 出现过的频次。哈希表初始置 count[0] = 1。时间复杂度 \(\mathcal{O}(N)\)。
LeetCode 532 - 数组中的 k-diff 数对 (K-diff Pairs in an Array) 中等
提示

差值 2-Sum (同向双指针或哈希)。
- 若 \(k = 0\)：统计频次 \(\ge 2\) 的不同元素个数；
- 若 \(k > 0\)：哈希集合去重后，枚举每个唯一键 \(x\)，检查集合中是否存在 \(x + k\)。
LeetCode 1010 - 总持续时间可被 60 整除的歌曲 (Pairs of Songs With Total Durations Divisible by 60) 中等
提示

同余 2-Sum (余数互补计数)。
- 长度模 60 得到余数 \(r \in [0, 59]\)。互补余数为 \((60 - r) \% 60\)。用大小为 60 的定长数组维护前缀余数频次，单次累加后更新。时间复杂度 \(\mathcal{O}(N)\)。
LeetCode 653 - 两数之和 IV - 输入 BST (Two Sum IV - Input is a BST) 简单
提示

BST 双栈模拟对撞双指针。
- 构建升序与降序两个双栈迭代器，分别指向树中最小值与最大值，模拟有序数组的对撞双指针逼近，达到严格 \(\mathcal{O}(N)\) 时间与 \(\mathcal{O}(\text{树高})\) 空间。