所有代码详见：https://github.com/jingminglake/Leetcode

总体思路

一、排序之后，双指针为何有效

把两数问题的解空间画成一张二维表，行是 left、列是 right，格子里是 nums[left] + nums[right]。数组排序之后这张表就有了单调性：left 往右走变大，right 往左走变小。

于是从右上角（left = 0，right = n - 1）出发，每一步都能有把握地排除一整行或一整列，而不是一个格子。原本 O(N^2) 的二重循环就压到了 O(N)。

这个”排除一整批”的性质是后面所有变种的地基。

二、两数之和：哈希还是双指针

1. Two Sum（无序，返回下标）

无序数组只能用哈希表，一遍扫描：对每个 nums[i] 去表里找 target - nums[i]，边扫边存。

一遍扫描为什么够？因为只考虑每个下标作为 pair 中较大的那一个，答案必然被覆盖到——详见《Leetcode总结（十二）》。

时间 O(N)，空间 O(N)。

167. Two Sum II（已排序，返回下标）

数组已排序，直接双指针：

vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) return {left + 1, right + 1};
        if (sum < target) left++;
        else right--;
    }
    return {};
}

时间 O(N)，空间 O(1)。

选哪个

	时间	空间	前提
哈希表	O(N)	O(N)	无
双指针	O(N)	O(1)	数组有序

结论：有序用双指针（省空间），无序用哈希表。无序数组若为了双指针而自己排序，要多花 O(NlogN)，反而不划算。

三、降维：kSum 的通用框架

三数问题的本质是降维成两数问题：固定一个数 nums[i]，剩下的部分就退化成”在子数组里找两个数凑出 target - nums[i]“。

推广开来，kSum 的通用解法是：前 k-2 层用循环固定，最后 2 层用双指针，时间 O(N^(k-1))。

排序
for i ...              # 固定第 1 个数
    for j = i+1 ...    # 固定第 2 个数（4Sum 才需要）
        left = j+1, right = n-1
        双指针

内层为什么从 i+1 开始

因为要避免重复使用同一个下标。外层已经占用了 i，内层若从 0 开始就可能再次选到 nums[i]，等于同一个数用了两次。从 i+1 出发，保证 i < left < right，三个位置互不相同。

这条对整个 kSum 家族通用：外层固定谁，内层就从谁的下一位开始。

18. 4Sum

两层外循环 + 内层双指针，O(N^3)，空间 O(1)。去重要做三处：外层 i 一处、外层 j 一处、内层 left/right 一处。

理论上有 O(N^2) 的哈希解（把所有 pair 的和存表再配对），但要保证四个下标互不相同、还要去掉值重复的四元组，实现极其繁琐，且空间 O(N^2)。实践中 O(N^3) 双指针就是最优解。

四、分岔口：去重还是计数

同一个双指针框架，题目要”返回内容”还是”返回数量”，走的是两条完全不同的路。

	要返回具体组合	只要数量
代表题	15、16、18	259、611、923
遇到重复值	跳过	数清楚

15. 3Sum —— 遇到重复要跳过

要返回所有不重复的三元组，所以两处都要去重：

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    for (int i = 0; i < n - 2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;          // 外层去重
        int left = i + 1, right = n - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                res.push_back({nums[i], nums[left], nums[right]});
                while (left < right && nums[left] == nums[left+1]) left++;      // 内层去重
                while (left < right && nums[right] == nums[right-1]) right--;
                left++; right--;                                                // 跳完还要各走一步
            }
        }
    }
    return res;
}

三个容易漏的点：

外层去重：nums[i] == nums[i-1] 就跳过。
内层去重：找到一个解后，left 向右、right 向左各自跳过所有相同值。因为同一个 i 下，位置不同但值相同的 pair 会产生完全一样的三元组。
跳完之后还要各再走一步，并继续扫描。这一步最容易漏——15 要找所有三元组，同一个 i 下内层可能存在多个不同的 pair 都成立。例如固定 i = -3，剩余数组 [-1, 1, 2, 4]，-1+4 和 1+2 都等于 3，找到第一个解不能退出，必须继续走到 left >= right。

去重的通用原则：一边计算一边去除，而不是算完了再统一去重。

16. 3Sum Closest —— 只留一个最优值

框架相同，但每步只做一件事：算出 sum，和已记录的最接近值比一比，更新即可。移动规则按 sum 与 target 的大小关系决定。

int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int res = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < n - 2; i++) {
        int left = i + 1, right = n - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (abs(sum - target) < abs(res - target)) res = sum;
            if (sum == target) return sum;
            if (sum < target) left++;
            else right--;
        }
    }
    return res;
}

注意：16 和 259 的扫描过程完全一样（left/right 交替往中间收，都走 O(N) 步，谁都不会”停在第一个”）。区别只在每一步做什么——16 更新一个最优值，259 累加一批计数。

259. 3Sum Smaller —— 一次数一整行

只要数量，不用去重（不同下标就是不同组合，即使值相同）。

int threeSumSmaller(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int res = 0, n = nums.size();
    for (int i = 0; i < n - 2; i++) {
        int left = i + 1, right = n - 1;
        while (left < right) {
            if (nums[i] + nums[left] + nums[right] < target) {
                res += right - left;   // left 打头的一整行都成立
                left++;
            } else {
                right--;
            }
        }
    }
    return res;
}

res += right - left 的含义：left 不动、right 从当前位置一路收到 left+1，这些组合全都满足，一次数完。

但这只消掉了一行，不是整张表。left 打头的数完了，left+1 打头的还没数——新的 nums[left] 变大了，可能就不满足了，所以要 left++ 继续判断。整个过程仍是 O(N) 步。

反过来，不满足时为什么只能动 right？因为当前 left 和更小的元素搭配可能仍是答案，不能丢；而当前 right 和任何元素搭配都必然超标，去掉无损失。

611. Valid Triangle Number —— 外层固定最大边

统计能构成三角形的三元组数量。排序后只需验 a + b > c（最小两边之和大于最大边），另外两个不等式自动成立。

关键差异：外层固定的是最大边，内层双指针在 [0, i-1] 上跑——和 15/259 正好相反。

int triangleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int res = 0;
    for (int i = nums.size() - 1; i >= 2; i--) {   // nums[i] 作为最大边
        int left = 0, right = i - 1;
        while (left < right) {
            if (nums[left] + nums[right] > nums[i]) {
                res += right - left;               // 最小的都配得上，中间全成立
                right--;
            } else {
                left++;
            }
        }
    }
    return res;
}

也可以降序排序，这样内层又变回熟悉的 left = i+1 形状，两者等价。但 Java 里基本类型数组无法直接降序排（Arrays.sort 不接受 comparator），所以实践中多用升序 + 外层倒着走。

923. 3Sum With Multiplicity —— 遇到重复要数清楚

统计满足 i < j < k 且三数之和等于 target 的下标三元组数量，对 1e9+7 取模。

这题是本系列最大的坑：命中目标值时，两边可能各有一整段重复值，移动任何一个指针都会漏掉组合。必须成段处理：

arr[left] != arr[right]：左边有 c1 个相同值、右边有 c2 个，两段任意搭配 → res += c1 * c2，然后整段跳过。
arr[left] == arr[right]：说明 [left, right] 整段同值，设长度 m，从 m 个里任选 2 个 → res += m*(m-1)/2，然后直接 break。

int threeSumMulti(vector<int>& arr, int target) {
    const int MOD = 1e9 + 7;
    sort(arr.begin(), arr.end());
    long res = 0;
    int n = arr.size();
    for (int i = 0; i < n - 2; i++) {
        int t = target - arr[i];
        int left = i + 1, right = n - 1;
        while (left < right) {
            if (arr[left] + arr[right] < t) left++;
            else if (arr[left] + arr[right] > t) right--;
            else if (arr[left] != arr[right]) {
                int c1 = 1, c2 = 1;
                while (left + 1 < right && arr[left] == arr[left+1]) { c1++; left++; }
                while (right - 1 > left && arr[right] == arr[right-1]) { c2++; right--; }
                res = (res + (long)c1 * c2) % MOD;
                left++; right--;
            } else {
                long m = right - left + 1;
                res = (res + m * (m - 1) / 2) % MOD;
                break;
            }
        }
    }
    return res;
}

15 和 923 的对照最能说明问题：同样是遇到一段重复值，15 的做法是跳过（因为值相同的三元组算重复），923 的做法是用组合数数清楚（因为下标不同就算不同答案）。

五、速查表

题号	题目	要什么	外层固定	内层要点	复杂度
1	Two Sum	下标	—	哈希一遍扫描	O(N) / O(N)
167	Two Sum II	下标	—	双指针	O(N) / O(1)
1099	Two Sum Less Than K	最大和	—	双指针，记录最优	O(NlogN)
15	3Sum	所有三元组	最小	三处去重 + 继续扫	O(N^2)
16	3Sum Closest	最接近的和	最小	每步更新最优	O(N^2)
18	4Sum	所有四元组	最小两个	三处去重	O(N^3)
259	3Sum Smaller	数量	最小	`res += right - left`	O(N^2)
611	Valid Triangle	数量	最大	`res += right - left`	O(N^2)
923	3Sum Multiplicity	数量	最小	成段计数 `c1*c2` / `C(m,2)`	O(N^2)

六、蓝图三问

看到一道新的 kSum 类题目，依次问：

数组有序吗？ 无序且只求两数 → 哈希；否则先排序。
要内容还是要数量？ 要内容就得去重（外层 + 内层 + 跳完继续走）；要数量就不去重，但要想清楚一次该加多少个。
外层该固定哪一个？ 大多数题固定最小的（内层从 i+1 开始），但像 611 这种由”最大边”定义合法性的题，固定最大的才顺。

Leetcode按题目类型总结（二十二）

排序双指针与 kSum 家族