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

总体思路

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

把两数问题的解空间画成一张二维表，行是 left、列是 right，格子里是 nums[left] + nums[right]，只看 left < right 的上三角。数组排序之后这张表就有了单调性：往右（right 增大）变大，往下（left 增大）也变大。

于是从右上角（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)。

走一遍 numbers = [1, 3, 4, 6, 8, 11]，target = 10：

每一步为什么安全：

• sum > target 时排掉一整列：当前 right 配上任何一个 left（只会更大）都还超标，这一列整体作废。
• sum < target 时排掉一整行：当前 left 配上任何一个 right（只会更小）都还不够，这一行整体作废。

选哪个

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

三、加与减：对向双指针与同向双指针

同样是两个指针，”求和”的题一头一尾相向而行，”求差”的题却是两个都从左边出发同向前进。原因藏在矩阵的单调性里。

用 a = [1, 3, 4, 6] 把两张表都填出来。

加法表（格子是 a[j] + a[i]）：

        j=1   j=2   j=3
i=0      4     5     7
i=1            7     9
i=2                 10

往右变大，往下也变大——两个方向同增。

减法表（格子是 a[j] - a[i]）：

        j=1   j=2   j=3
i=0      2     3     5
i=1            1     3
i=2                  2

往右（j++）变大——减数不变、被减数变大； 往下（i++）变小——被减数不变、减数变大。

你需要一个既能”调大”又能”调小”的起点，这就决定了几何形状：

减法表里这两个动作都朝前，指针永不回退，这也解释了为什么求差的题里 right 不用重置。

532. K-diff Pairs in an Array

求差的代表题，详细解法见《Leetcode总结（二）》和《Leetcode总结（十二）》。这里补两条那两篇没写的道理：

（1）为什么必须同向——就是上面那张表。nums[right] - nums[left] 要变大得 right++，要变小得 left++，两个操作都往右，没法一头一尾。

（2）单调性省的是什么——不是用来”找”那个数的，是保证不用重新找。

“固定 left，去右边找 nums[left] + k“这个思路本身没错，但如果每次都从 left+1 重扫或二分，那是 O(N^2) 或 O(NlogN)。单调性给的是：left 右移后 nums[left] 变大，目标值 nums[left] + k 也跟着变大，所以匹配的 right 只可能在原位置的右边，绝不回退。于是 right 全程只增不减，两个指针加起来 O(2N)——这就是摊还，和《总结（二十一）》滑动窗口那套论证是同一个。

其实 532 的同向双指针本质上就是个滑动窗口：窗口是 [left, right]，窗口值 nums[right] - nums[left] 太小就扩右边、太大就收左边，可变窗口的蓝图直接能套。

两种形状省的东西不同：

• 对向双指针靠有序性排除整行整列
• 同向双指针靠单调性避免回退

四、降维：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. 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;
}

三个容易漏的点：

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

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

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

框架相同，但每步只做一件事：算出 sum，和已记录的最接近值比一比，更新即可。

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;
}

拿 nums = [-2, 0, 1, 3]、target = 2 走一遍。i = 0（值 -2），内层目标 target' = 2 - (-2) = 4，子数组是下标 1~3 的 [0, 1, 3]：

i = 1（值 0），target' = 2，子数组 [1, 3]：1+3 = 4 ≥ 2 → right-- → 结束，加 0。总计 2，对应 [-2,0,1] 和 [-2,0,3]。

两条排除逻辑（这是全题的核心）：

• 满足时：nums[right] 已经是右边最大的，它都行，比它小的更行 → left 配上 [left+1, right] 里任何一个都合法，res += right - left 一次数完。这一行数完了可以整行退休 → left++。
• 不满足时：nums[left] 已经是左边最小的，它配 right 都超标，比它大的更超标 → right 跟剩下任何人都组不成合法对，整列作废 → right--。

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

伪代码形态：

sort(nums)
res = 0
for i = 0 to n-3:                    # 固定最小的数
    left  = i + 1                    # 右上角起点
    right = n - 1
    while left < right:              # 结束条件：两指针相遇
        sum = nums[i] + nums[left] + nums[right]
        if sum < target:
            res += right - left      # 这一行全合法，批量记账
            left++                   # 往下：这一行退休
        else:
            right--                  # 往左：这一列作废
return res

每一步只有一个动作，不存在分叉：两个条件互斥且穷尽，看当前格子的值就唯一确定往哪走，不需要看邻居。终止性也是显然的——每轮必定移动一个指针且都朝对方靠拢，最多 n-1-i 步相遇。

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 的做法是用组合数数清楚（因为下标不同就算不同答案）。

六、单边与双边：区间条件怎么拆

2563. Count the Number of Fair Pairs

统计满足 0 <= i < j < n 且 lower <= nums[i] + nums[j] <= upper 的下标对数量。

为什么不能直接双指针：双边约束下，sum 落在区间外时没法用一个 right - left 批量数——那一行里可能一部分太小、一部分太大，合法段悬在中间。而单边约束才有”合法的一定是连续一整段且贴着一端”这个性质。

解法：把区间拆成两个单边之差。

lower <= sum <= upper
   等价于
(sum <= upper 的对数) − (sum < lower 的对数)

       < lower  |  lower ≤ sum ≤ upper  |  > upper
       └────────┴───────────────────────┘
              全是 ≤ upper 的
       └────────┘
        要减掉的

拆完之后每一半都退回成 259，一次数一整行：

long countLE(vector<int>& nums, long X) {   // 和 <= X 的对数
    long res = 0;
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        if ((long)nums[left] + nums[right] <= X) {
            res += right - left;    // left 打头的一整行都成立
            left++;
        } else {
            right--;
        }
    }
    return res;
}

long long countFairPairs(vector<int>& nums, int lower, int upper) {
    sort(nums.begin(), nums.end());
    return countLE(nums, upper) - countLE(nums, lower - 1);
}

排序不影响答案，因为只关心 i < j 的对数，重排不改变对的总数。

跑一遍 nums = [0,1,7,4,4,5]、lower = 3、upper = 6，排序后 [0,1,4,4,5,7]。countLE(6)：

countLE(2) = 1（只有 0+1）。答案 7 - 1 = 6 ✓

这个套路叫”前缀之差”

《总结（二十一）》滑动窗口篇里 992 那条”恰好 k = 至多 k − 至多 k-1”是同一个东西：

通用原则：双边或”恰好”型条件不好直接双指针/滑窗，就拆成两个单边条件相减。见到”恰好”“区间内”这类字眼，先想能不能这么拆。

七、边界：等号归哪一边

上表第三步 sum == 6 正是等号情形，走的是满足支。批量记账在等号时依然成立：若 nums[left] + nums[right] == X，则 [left+1, right] 里任何 m 都有 nums[m] <= nums[right]，故 nums[left] + nums[m] <= X，整行合法。

这个等号有实际后果：若误判成”不满足”去做 right--，上例会算出 6，减去 countLE(2)=1 得 5，答案就错了（正确是 6）。

三题的边界并排看：

注意 259 和 countLE 的等号移动方向正好相反。所以别把”等号时往大的方向走”当规律记——换一题就翻。正确的推导是两步，中间不能跳：

第一步：等号归哪一支？          ← 由题目符号决定（≤ 还是 <）
第二步：那一支的固定动作是什么？  ← 满足就 left++，不满足就 right--

方向是这两步推出来的结果，不是可以直接背的规律。259 若要复用 countLE，就是 countLE(target - 1)——这也是 2563 里那个 lower - 1 的来历。

八、速查表

九、心智模型：双指针不是搜索

这一节是我卡了最久才想通的东西，单独记下来。

不存在”逼近”

和值不会朝 target 收敛，它一路上下跳，可能一直大、一直小、来回换。哪一步动 left、哪一步动 right，完全由数据决定，路径形状事先看不出来。

但有一条是绝对刚性的：left 只增，right 只减，谁都不回头。这保证了终止和 O(N)。

没规律的是移动，刚性的是不变量。

正确性不来自路径

正确性来自每一步都维持的那个不变量：

所有还没数过的合法对，一定都落在 [left, right] 里面。

每次移动之前都先证明”被扔掉的那一行/一列不含未数过的合法对”，然后才扔。路径是这个过程的副产品，不是设计出来的。

所以看双指针题不该问”我怎么走过去”，该问”我凭什么敢扔掉这一行“。答得出后者，路径自然就对了。

和二分查找划清界限

“逼近”这个直觉不是凭空来的——它是二分查找的正确模型。把最邻近的算法迁移过来是合理的，只是边界没划清：

167 看起来像”瞄准型”（找到就返回），但它的正确性依然来自排除而非逼近——只是恰好提前撞上了答案。

不确定动哪个指针时

别问”该往哪走”，问”这一行数完了吗“。

数完了 → 动 left（整行退休）；没数完说明这一列废了 → 动 right。

十、蓝图三问

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

1. 是加还是减？ 加 → 对向双指针（一头一尾）；减 → 同向双指针（都从左边出发）。无序且只求两数 → 直接哈希。
2. 条件是单边还是双边？ 单边（< / >）→ 直接双指针；双边或”恰好”→ 拆成两个单边相减（前缀之差）。
3. 要内容还是要数量？ 要内容就得去重（外层 + 内层 + 跳完继续走）；要数量就不去重，但要想清楚一次该加多少个，以及等号归哪一支。

外层固定哪一个：大多数题固定最小的（内层从 i+1 开始），但像 611 这种由”最大边”定义合法性的题，固定最大的才顺。

• 上一篇
  Leetcode按题目类型总结（二十一）