1. 项目概述
双指针算法是解决数组和链表问题的利器，在LeetCode高频题目中占比超过20%。这个专题我刷了3遍Hot 100榜单，发现双指针类题目往往代码简洁但思维难度大，特别适合用C++这种性能敏感型语言来实现。本文将拆解6类经典双指针场景，包含15道高频题目的完整题解，每道题都标注了时间复杂度分析和个人刷题心得。
2. 双指针核心原理
2.1 算法思想本质
双指针通过维护两个指针变量，在单次遍历中完成传统暴力解法需要嵌套循环的任务。其核心优势在于：
- 空间复杂度通常为O(1)
- 时间复杂度从O(n²)优化到O(n)
- 特别适合处理有序数据
2.2 C++实现要点
cpp复制// 典型双指针框架
int left = 0, right = nums.size() - 1;
while (left < right) {
if (condition) {
// 处理逻辑
left++;
} else {
right--;
}
}
注意事项：
- 初始边界要严格验证空数组等特殊情况
- 移动指针时要考虑相等情况的处理
- 循环终止条件决定最终结果位置
3. 六大应用场景详解
3.1 相向指针（对撞指针）
典型题目：167.两数之和II、15.三数之和
代码模板：
cpp复制sort(nums.begin(), nums.end()); // 必须先排序
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
// 记录结果
while (left < right && nums[left] == nums[left+1]) left++; // 去重
left++;
}
else if (sum < target) left++;
else right--;
}
避坑指南：
- 三数之和需要额外固定一个基准点
- 去重逻辑必须放在找到有效解之后
- 当输入规模>10^4时，暴力法必然超时
3.2 快慢指针
典型题目：141.环形链表、142.环形链表II
Floyd判圈算法：
cpp复制ListNode* slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
// 找入口点
ListNode* ptr = head;
while (ptr != slow) {
ptr = ptr->next;
slow = slow->next;
}
return ptr;
}
}
复杂度分析：
- 时间复杂度：O(n)
- 空间复杂度：O(1)
- 数学证明：相遇时slow未走完一圈
3.3 滑动窗口
典型题目：3.无重复字符的最长子串、76.最小覆盖子串
模板代码：
cpp复制unordered_map<char, int> window;
int left = 0, right = 0;
while (right < s.size()) {
char c = s[right++];
window[c]++;
while (window[c] > 1) { // 收缩条件
char d = s[left++];
window[d]--;
}
res = max(res, right - left);
}
优化技巧：
- 用vector代替unordered_map可提升20%性能
- 预先记录needle字符可减少无效判断
- 当字符集有限时可用数组替代哈希表
4. 高频题目精讲
4.1 接雨水问题（42题）
三维视角解法：
cpp复制int left = 0, right = height.size() - 1;
int left_max = 0, right_max = 0;
int res = 0;
while (left < right) {
if (height[left] < height[right]) {
height[left] >= left_max ?
(left_max = height[left]) : res += left_max - height[left];
left++;
} else {
// 对称处理右指针
}
}
关键理解：
- 每列雨水高度由min(左边最高,右边最高)决定
- 时间复杂度O(n)优于动态规划的O(n²)
- 边界条件处理要特别注意0高度列
4.2 移动零（283题）
原地操作技巧：
cpp复制int slow = 0;
for (int fast = 0; fast < nums.size(); fast++) {
if (nums[fast] != 0) {
swap(nums[slow++], nums[fast]);
}
}
易错点：
- 不能简单覆盖要保留交换
- slow指针始终指向下一个非零元素的位置
- 循环结束后不需要额外补零
5. 调试与优化技巧
5.1 可视化调试法
对于复杂指针问题，建议：
- 在纸上画出指针移动示意图
- 标注每次循环后的指针位置
- 特别关注边界条件：
- 空输入
- 全相同元素
- 极值情况
5.2 性能优化checklist
- 避免不必要的容器拷贝
- 使用reserve预分配内存
- 用++i替代i++减少临时对象
- 对有序数据优先考虑二分
6. 专题扩展训练
6.1 同类题目推荐
- 链表的中间节点（876）
- 平方数之和（633）
- 四数之和（18）
- 最接近的三数之和（16）
6.2 组合题型
当双指针与其他算法结合时：
- 双指针+二分：缩短搜索范围
- 双指针+哈希：快速查找补数
- 双指针+堆：处理多指针场景
我在刷完这个专题后总结出三条经验：第一是必须手动画图理解指针移动逻辑；第二是相同题型要对比记忆；第三是C++实现时要注意迭代器失效问题。建议每道题先自己实现，再对比最优解，重点分析思维差异点。