所有代码详见：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 的来历。

八、速查表

九、当单调性不来自数据：11. Container With Most Water

前面八节所有题目的地基都是同一句话：数组排序之后，那张二维表才有了单调性。11 题是个反例——它根本不排序（一排序柱子的位置就毁了），但对向双指针照样成立。

原因是：单调性可以由公式提供，不一定要由数据提供。

题意与暴力解

给出 height 数组表示一排柱子的高度，任选两根装水，问最大面积。

area(l, r) = min(h[l], h[r]) × (r - l)

暴力就是枚举所有 (l, r)，O(N^2)。双指针要做的事，是把这 N^2 个候选里的绝大多数，成批地证明为”不可能更优”然后扔掉。

骨架（先记这六行）

① 面积 = min(h[l], h[r]) × (r - l)。min 意味着「矮的那根封顶」
② 从两端起步 → 宽度只减不增 → 当前这一对永远是各自够得着的最远伙伴
③ 矮的那根：正在最宽处 + 高度已封顶 → 巅峰就是现在 → 扔掉不丢解
④ 高的那根：被对面拖累着还没发挥完 → 不能扔
⑤ 相等：两根同时到顶，移任一根都行，甚至可以一起移
⑥ 答案 = res 取过程峰值（面积并不单调！）

易错（2026-09-21 复习实测答错的就是这条）

「移动矮的那根」保证的不是「结果单调变大」。

[1,8,6,2,5,4,8,3,7] 的面积序列是 8 → 49 → 18 → 40 → 16 → 15 → 4 → 6——一路上下跳，最大值出现在第 2 步。靠的是 res = max(...) 兜住峰值，不是靠单调。

它真正保证的是：扔得起——被扔掉的那根已经到顶，它的最优搭档刚刚算过。（对照 42 保证的是另一件事：算得准——那一格的水量可以当场定死。）

正确性不要求每步都变好，只要求不漏解。「每步都赚」是贪心的要求，「不漏解」才是排除法的要求。

第一根支柱：min 制造天花板

min 的物理含义是木桶原理——水面是平的，高度由矮的那块板决定，高的那块超出的部分水从旁边溢走了，白高。

但 min 真正的作用是制造了一种不对称。设 h[l] = 3，h[r] = 8：

• 对 l 来说：它这辈子的高度上限就是 3，因为无论右边站着谁，min(3, ·) ≤ 3。它已经到顶了。
• 对 r 来说：它的上限是 8，但此刻只发挥到 3（被 l 拖累）。换个更高的左端点，它还能涨。它还有余地。

是 min 这个函数本身，制造了”谁已到顶、谁还有余地”的区别。一个二维的枚举 (l, r)，被 min 降成了”当前瓶颈是谁”的一维问题。

反过来验证：如果面积改成 max(h[l], h[r]) × (r - l)，双指针立刻崩塌，而且不是”改成移动高的”就能救——是两端谁都扔不掉。因为 max 没有天花板，任何一端的高度都可能被对面顶上去，于是任何候选都无法被证明出局。

• 反例（移动高的）：[1, 100, 1, 1, 2]，答案 300（下标 1 和 4），第一步就把下标 4 扔了，只能得 100。
• 反例（移动矮的）：[2, 100, 1, 1, 1]，答案同样是 300，第一步同样把下标 4 扔了。

第二根支柱：从两端起步，把”宽”钉成单调

面积 = 高 × 宽，两个因子互相拉扯，二维的东西没法剪枝。

从最宽的 (0, n-1) 起步、只向内收，等于强行把「宽」变成一个只减不增的量。于是每一步的问题从二维塌成一维：「高」涨的那点，够不够补「宽」减的那点？

更要紧的是，这保证了另一件事：当前这一对 (l, r)，永远是 l 和 r 各自还够得着的最远伙伴。”退休”的论证完全依赖这一点——说一根柱子”到顶了”，前提是它正站在自己能达到的最大宽度上。

如果从中间往外扩，宽度在涨、高度也可能涨，两个因子同时可能变好，任何候选都不敢扔，只能老实 O(N^2)。

对向双指针从两端起步，从来不是”习惯”，而是为了让某个量单调。11 题让宽度单调，kSum 让和单调。

合起来：矮的那根可以退休

两根支柱合起来才成立：

矮的那根柱子，正处在它这辈子最宽的位置（支柱二），再往里走只会更窄；而它的高度又被自己封了顶（支柱一），涨不上去。所以它的巅峰就是现在，算完即可扔。

而高的那根绝不能扔——它此刻被对面拖累着，还没发挥完。

int maxArea(vector<int>& height) {
    int l = 0, r = height.size() - 1, res = 0;
    while (l < r) {
        res = max(res, min(height[l], height[r]) * (r - l));
        if (height[l] < height[r]) l++;   // 矮的那根退休
        else r--;
    }
    return res;
}

两边相等怎么办

h[l] == h[r] 时，移哪根都可以。

理解的关键是”极限”这个词：以矮的那根为边时，另一侧已经取到极限了——当前对面那根就是它能够得着的最远伙伴，再往里只会更窄，而它自己的高度又封了顶。所以它的最优结果已经产生了，可以退休。

等高的时候，两侧同时都到了极限：

• 以 l 为边：任何 r' < r 都有 min(h[l], h[r']) ≤ h[l]，宽度更窄 → 全部 ≤ 当前值
• 以 r 为边：任何 l' > l 都有 min(h[l'], h[r]) ≤ h[r]，宽度更窄 → 全部 ≤ 当前值

两条论证完全对称地成立，谁都不存在”被对面拖累、还有余地”这回事。所以下面三种写法都对：

if (h[l] < h[r]) l++; else r--;        // 相等时移 r
if (h[l] <= h[r]) l++; else r--;       // 相等时移 l

if (h[l] < h[r]) l++;                  // 相等时两根一起退休
else if (h[l] > h[r]) r--;
else { l++; r--; }

第三种是个微优化（省一次循环）：既然两根都已到极限，含 l 的和含 r 的候选全部被判死了，剩下的最优解只可能落在 (l+1, r-1) 里面。不写也完全正确，但如果觉得”一起移会不会漏解”，说明退休论证还没吃透。

和 kSum 的等号对比：同样是”等号归哪边”，性质完全不同。

区别在于：kSum 的等号决定这一批候选算不算数（直接影响计数结果）；11 的等号只决定先扔谁（两批候选都已判死，扔的顺序不影响答案）。

等号自由，是因为两边的退休论证都已经独立成立了。

那些没被算到的组合去哪了：一次对账

这是最容易被跳过的一环。双指针根本不覆盖所有 (i,j)——n=9 一共 C(9,2) = 36 对，它只算了 8 对，剩下 28 对碰都没碰。那 28 对凭什么不用算？

答案是：每扔一根柱子，就把所有还没算过的、含这根柱子的组合一次性连坐判死。

以 h = [1,8,6,2,5,4,8,3,7] 为例：

对账：算过 8 对 + 排除 7+6+5+4+3+2+1+0 = 28 对 = 36 对，正好是 C(9,2)。一对不多，一对不少。

每一个组合要么被真算了，要么被证明出局了，没有第三种命运。这才是”不漏解”的完整含义——不是全都看了，是全都处理了。

再注意第 2 步的推理：排除 (2,8) 到 (7,8) 这 6 对时，它们的值我一个都没看。下标 2~7 的高度是多少完全不影响结论，因为 min 把它们全压在 7 以下了。

排除是结构性的，不是数值性的。靠的是 min 封顶 + “当前最宽”这两个结构事实，不需要查看被排除者的值。

如果每次排除都得去看那批候选的值，那还是 O(N^2)。这才是它能做到 O(N) 的真正原因。

最后一块：路径根本搞不清，也不需要搞清

这题最劝退的地方在于：每次往哪边移动，取决于两边的高度，完全是动态的。解空间的形状想象不出来，只知道”某个点还有向上增长的潜力”，至于走到这一步之前发生了什么，根本搞不清。

搞不清是对的——这条路径完全由数据决定，改一个数顺序就全变了，它不携带任何信息，也不该去追踪。

撑住整个算法的是一句在任何路径下都成立的话：

循环不变量：已经被扔出 [l, r] 之外的每一根柱子，它参与的所有组合面积都 ≤ res。 等价说法：如果最优解还没被算到，那它的两个端点一定都还在 [l, r] 里面。

不变量把”过去发生过什么”整个封装掉了。终止时 l == r，区间里塞不下任何一对，而不变量说最优解的两端都还在区间内——现在区间内没有对了，说明最优解已经被算过。证毕。整个证明里一次都没提过路径。

这也解释了为什么二分查找好懂而双指针难懂：

二分能在脑子里跟着走完一遍，所以踏实；双指针跟不了，于是总觉得”少了点什么”。少的不是理解，是一种本来就不该依赖的理解方式。

所以收口是这样一句：

我们从不追问”哪个点将来会成为答案”，只反复回答一个局部问题：眼前这两根，哪一根已经没有潜力了？ 把没潜力的踢掉，res 自己会留下见过的最大值。答案不是被找到的，是被剩下的。

与 kSum 家族的对照

双指针能不能用，不取决于有几个指针，取决于能不能证明某个端点已经出局。

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

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

不存在”逼近”

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

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

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

正确性不来自路径

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

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

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

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

和二分查找划清界限

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

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

不确定动哪个指针时

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

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

十一、蓝图三问

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

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

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

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