5
双指针思想笔记（C++版）
一句话理解
> 双指针：用两个“箭头”在数组或字符串上移动，解决需要比较、查找、反转等问题。
就像两个人同时在一条路上走，有时一起走，有时面对面走，用他们的位置关系来解决问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
一、什么是双指针？
双指针：使用两个指针（下标）来遍历数据结构，通过移动指针来高效解决问题。
核心思想：利用两个指针的位置关系，减少循环的层数，把 O(n²) 变成 O(n)。
常见类型：
* 左右指针：一个在左，一个在右，向中间移动
* 快慢指针：一个走得快，一个走得慢
* 同向指针：两个都从左边开始，一前一后
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、左右指针（对撞指针）
题目1：两数之和（洛谷P1102）
题目描述：给定 n 个从小到大排好序的整数和一个目标数 target，请找出两个数，使它们的和等于 target。输出这两个数的下标（从1开始）。题目保证有唯一解。
输入样例：
输出样例：
（因为 a[2]=2, a[4]=6，和是8）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目2：回文判断（洛谷P1015）
题目描述：给定一个字符串，判断它是否是回文串（正着读和倒着读一样）。字符串长度不超过1000。
输入样例：
输出样例：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目3：盛最多水的容器（洛谷P1652）
题目描述：给定 n 个非负整数 a[1], a[2], ..., a[n]，每个数代表坐标中的一个点 (i, a[i])。找出两条线，使得它们与 x 轴构成的容器能容纳最多的水，输出最大面积。
思路：左右指针，每次移动高度较小的那个指针。
输入样例：
输出样例：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、快慢指针
题目4：删除有序数组中的重复项（洛谷P1116）
题目描述：给定一个有序数组，删除重复出现的元素，使每个元素只出现一次，返回新数组的长度。不要使用额外数组，必须在原数组上操作。
输入样例：
输出样例：
（去重后前4个位置：1 2 3 4）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目5：找出数组的中间位置
题目描述：给定一个数组，找出它的中间位置。如果数组长度是奇数，输出正中间的下标；如果是偶数，输出靠左的那个中间下标。
输入样例1：
输出样例1：
输入样例2：
输出样例2：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、同向指针
题目6：移除元素（洛谷P1177）
题目描述：给定一个数组和一个值 val，原地移除所有数值等于 val 的元素，返回新数组的长度。元素的顺序可以改变。
输入样例：
输出样例：
（剩余元素：1 3 4 5 6 7 8）
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目7：把0移到末尾（洛谷P1111）
题目描述：给定一个数组，把所有的0移到数组的末尾，同时保持非零元素的相对顺序。
输入样例：
输出样例：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、双指针常见题型总结
类型 指针移动方式 经典题目 左右指针 一左一右，向中间移动 两数之和、回文判断、盛水容器 快慢指针 一快一慢，快慢速度不同 数组去重、找中点 同向指针 一前一后，都向右移动 移除元素、移动零
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、时间复杂度对比
方法 时间复杂度 空间复杂度 暴力双重循环 O(n²) O(1) 双指针 O(n) O(1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、易错点
易错点 正确做法 下标从0开始还是从1开始 本笔记统一从1开始 左右指针需要数组有序 两数之和、盛水容器需要有序 循环条件写错 左右指针用 left < right 快慢指针边界 注意 fast + 1 <= n 防止越界
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、总结
要点 内容 核心思想 用两个指针减少循环层数 时间复杂度 O(n) 空间复杂度 O(1) 适用场景 数组、字符串相关问题 下标习惯 本笔记统一从1开始
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
记忆口诀
> 双指针，真神奇，两个箭头来回移
> 左右指针向中间，两数和与回文题
> 快慢指针一快慢，去重找中点搞定
> 同向指针一前后，移除元素移零灵
> 暴力循环 n 平方，双指针 n 就搞定
> 下标统一从1起，边界判断要仔细
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
有帮助，赞一个