c++中如何使用双指针解决字符串问题_c++双指针处理字符串方法-C++-PHP中文网

c++中如何使用双指针解决字符串问题_c++双指针处理字符串方法

冰火之心

发布： 2025-09-30 18:33:02

原创

692人浏览过

双指针通过两个索引高效处理字符串，如回文判断用对撞指针、去重或移字符用快慢指针，典型应用包括忽略非字母数字的回文检测、翻转单词顺序及移动特定字符至末尾，均在O(n)时间与O(1)空间完成。

c++中如何使用双指针解决字符串问题_c++双指针处理字符串方法

在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;

登录后复制

}

这个方法逐个比较首尾字符，跳过无效字符，直到两指针相遇。

Robovision AI

一个强大的视觉AI管理平台

查看详情

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;
}

登录后复制

快指针遍历，慢指针记录非目标字符的位置，最后补上 '*'。

基本上就这些常见模式。掌握对撞与快慢双指针，能简洁高效地解决多数字符串操作问题。关键是理清两个指针的移动条件和终止时机。不复杂但容易忽略细节，比如边界判断和字符有效性检查。

以上就是c++++中如何使用双指针解决字符串问题_c++双指针处理字符串方法的详细内容，更多请关注php中文网其它相关文章！