C++ 双指针入门与常见陷阱：从数组理论到二分法（含 LeetCode 解法对比）

这篇文章给你一个“能在面试和刷题里直接复用”的框架：

1. 双指针为什么常和数组绑定在一起？
2. 二分法为什么本质上是“边界搜索”？
3. 常见 bug 都卡在哪些细节？
4. 面对 LeetCode 题目，如何在多种解法中做取舍？

---

1. 数组的理论基础：为什么它是双指针和二分法的主战场？

数组有两个关键属性：

• 连续内存：支持 O(1) 随机访问（a[i]）
• 有序性可维护：排序后可利用“单调性”做二分

因此：

• 双指针依赖“可按下标线性推进”的结构
• 二分法依赖“答案空间或数据空间单调”

一句话概括：

数组 = 可定位（随机访问）+ 可比较（有序/可构造单调），这正是双指针和二分法高效的基础。

---

2. 双指针基础：四种最常见模型

2.1 对撞指针（left/right）

适合有序数组，用于：

• 两数之和
• 去重
• 回文判断

vector<int> twoSumSorted(vector<int>& nums, int target) {
    int l = 0, r = (int)nums.size() - 1;
    while (l < r) {
        int s = nums[l] + nums[r];
        if (s == target) return {l, r};
        if (s < target) ++l;
        else --r;
    }
    return {-1, -1};
}

2.2 快慢指针（slow/fast）

适合“原地删除/压缩”类问题：

• 删除有序数组重复项
• 移动零

核心思想：

• fast 负责扫描
• slow 负责写入下一个有效位置

2.3 滑动窗口（本质也是双指针）

[l, r] 表示当前窗口，右指针扩张，左指针收缩。用于：

• 最长/最短子串
• 和/频次约束子数组

2.4 三指针（双指针扩展）

典型是三数之和：

• 外层固定一个 i
• 内层 l/r 做 two-sum

---

3. 双指针高频陷阱（C++ 实战版）

1. 边界条件写错：l <= r 和 l < r 混用。对撞题通常是 l < r。
2. 去重时机错：三数之和中应在找到解后对 l/r 去重，且外层 i 也要去重。
3. 先写后移 vs 先移后写 混乱：快慢指针必须先明确“写入语义”。
4. 整型溢出：nums[l] + nums[r] 可能溢出，必要时用 long long。
5. 引用失效/越界：循环内更新指针后立刻访问新位置，要先判边界。

---

4. 二分法基础：不是找数字，而是找边界

很多人把二分写成“查某个值”，但更通用的表述是：

• 找到第一个满足 check(mid)=true 的位置（lower bound）
• 或最后一个满足条件的位置（upper bound 变体）

4.1 推荐模板（左闭右开）

int lowerBound(const vector<int>& a, int target) {
    int l = 0, r = (int)a.size(); // [l, r)
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= target) r = mid;
        else l = mid + 1;
    }
    return l;
}

优点：

• 不会出现 r = mid - 1 带来的复杂性
• 循环结束时 l == r，语义清晰

4.2 二分法常见陷阱

1. mid = (l + r) / 2 可能溢出（理论上）→ 用 l + (r - l) / 2
2. 区间定义不统一：[l, r] 和 [l, r) 混用导致死循环
3. 更新规则不对称：例如 l = mid 导致卡死（应 l = mid + 1）
4. 忘记后验校验：返回位置不一定合法（需判断是否越界/是否等于目标）

---

5. LeetCode 题目解法与对比

5.1 Two Sum（#1）

• 解法 A：暴力 O(n²)
• 解法 B：哈希表 O(n)
• 解法 C（若已排序）：双指针 O(n)

对比：

• 未排序数组首选哈希
• 已排序数组首选双指针（更省空间）

5.2 Two Sum II - Input Array Is Sorted（#167）

标准对撞双指针，O(n) 时间 / O(1) 空间。

vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0, r = (int)numbers.size() - 1;
    while (l < r) {
        long long s = 1LL * numbers[l] + numbers[r];
        if (s == target) return {l + 1, r + 1};
        if (s < target) ++l;
        else --r;
    }
    return {};
}

5.3 Remove Duplicates from Sorted Array（#26）

快慢指针模板题。

• fast 扫描新元素
• 若与 nums[slow] 不同，则 ++slow 并写入

复杂度 O(n) / O(1)。

5.4 3Sum（#15）

排序 + 外层枚举 + 内层双指针，复杂度 O(n²)。

关键不是“会写”，而是去重正确：

• i > 0 && nums[i] == nums[i-1] 跳过
• 找到答案后 while 去重 l 和 r

5.5 Valid Palindrome（#125）

双指针从两侧向中间收缩，过程中跳过非字母数字字符。

考点：

• 指针推进顺序
• isalnum/tolower 的使用与字符转换安全

5.6 Binary Search（#704）

最基础二分模板题，建议一开始就固定“左闭右开”模板，后续迁移到：

• 搜索插入位置（#35）
• 在排序数组中查找元素第一个和最后一个位置（#34）

5.7 Find First and Last Position of Element（#34）

本质是两次二分：

• 左边界 = lower_bound(target)
• 右边界 = lower_bound(target + 1) - 1

对比价值：

• 比“命中后向两边扩展”更稳定，最坏仍 O(log n)

---

6. 双指针 vs 二分法：如何选？

• 双指针：更偏“扫描与维护”，常用于线性结构约束问题（和、去重、窗口）
• 二分法：更偏“单调性判定”，常用于有序数组或答案空间搜索

经验法则：

1. 看到“有序 + 两端逼近”→ 先想双指针
2. 看到“有序 + 查边界”→ 先想二分
3. 看到“最小值最大化/最大值最小化”→ 想答案二分 + check()

---

7. 一份实战检查清单（面试前背这个）

• 双指针：
  • 我定义的是对撞/快慢/窗口哪一种？
  • 循环不变量是什么？
  • 指针移动后是否会越界？
  • 去重放在哪个时机？
• 二分：
  • 区间是 [l, r] 还是 [l, r)？
  • mid 和更新规则是否匹配区间定义？
  • 返回值含义是否是“插入点/第一个满足条件的位置”？
  • 是否做了最终合法性校验？

---

8. 总结

把这两个主题真正学会，不是背模板，而是掌握三件事：

1. 数据结构属性（数组的随机访问与有序性）
2. 循环不变量（每一步为什么合法）
3. 边界语义（何时停、停下后返回什么）

当你把“思路 + 模板 + 陷阱”统一起来后，LeetCode 中大量中等题会从“靠记忆”变成“可推导”。