双指针通过两个索引高效处理字符串，如回文判断用对撞指针、去重或移字符用快慢指针，典型应用包括忽略非字母数字的回文检测、翻转单词顺序及移动特定字符至末尾，均在O(n)时间与O(1)空间完成。
在C++中，双指针是一种高效处理字符串问题的技巧，尤其适用于需要比较或操作字符串中两个不同位置元素的场景。它通过使用两个指向字符的指针，从两端或同一方向移动，避免使用额外空间或嵌套循环，从而提升效率。
1. 双指针的基本思想
双指针通常定义两个索引变量（或迭代器），分别指向字符串中的不同位置：
- 对撞指针：一个从头开始，一个从尾开始，相向移动，常用于回文判断、翻转等。
- 快慢指针：都从开头出发，快指针先走，用于去重、删除特定字符等。
这种方法将时间复杂度控制在 O(n)，空间复杂度为 O(1)。
2. 判断回文字符串
使用对撞指针判断一个字符串是否为回文（忽略大小写和非字母数字字符）：
立即学习“C++免费学习笔记（深入）”；
bool isPalindrome(string s) {
int left = 0, right = s.size() - 1;
while (left < right) {
// 跳过非字母数字字符
while (left < right && !isalnum(s[left])) left++;
while (left < right && !isalnum(s[right])) right--;
<pre class='brush:php;toolbar:false;'> if (tolower(s[left]) != tolower(s[right]))
return false;
left++;
right--;
}
return true;}
这个方法逐个比较首尾字符，跳过无效字符，直到两指针相遇。
3. 翻转字符串中的单词顺序
例如将 "the sky is blue" 变成 "blue is sky the"，可以分三步：
- 整体翻转字符串
- 逐个翻转每个单词
- 用快慢指针去除多余空格
核心是利用双指针原地调整：
void reverseWords(string& s) {
// 去除多余空格
int slow = 0;
for (int fast = 0; fast < s.size(); fast++) {
if (s[fast] != ' ') {
if (slow != 0) s[slow++] = ' '; // 单词间加一个空格
while (fast < s.size() && s[fast] != ' ')
s[slow++] = s[fast++];
}
}
s.resize(slow);
<pre class='brush:php;toolbar:false;'>// 整体翻转
reverse(s.begin(), s.end());
// 每个单词再翻转
int start = 0;
for (int i = 0; i <= s.size(); i++) {
if (i == s.size() || s[i] == ' ') {
reverse(s.begin() + start, s.begin() + i);
start = i + 1;
}
}}
4. 移动字符或去重
比如将字符串中的所有 '*' 字符移到末尾，保持其他字符顺序不变：
string moveStarsToEnd(string s) {
int slow = 0;
for (int fast = 0; fast < s.size(); fast++) {
if (s[fast] != '*') {
s[slow++] = s[fast];
}
}
while (slow < s.size()) s[slow++] = '*';
return s;
}
快指针遍历，慢指针记录非目标字符的位置，最后补上 '*'。
基本上就这些常见模式。掌握对撞与快慢双指针，能简洁高效地解决多数字符串操作问题。关键是理清两个指针的移动条件和终止时机。不复杂但容易忽略细节，比如边界判断和字符有效性检查。
