为何时间复杂度为O(n)的回文判断代码耗时达54ms？

核心耗时原因：s.erase() 操作的高复杂度 #

你的代码中，遍历字符串时遇到非字母数字字符就调用 s.erase(s.begin()+n)，这个操作的时间复杂度是O(k)（k为删除位置到字符串末尾的字符数）。如果原字符串存在大量非字母数字字符，该操作会被多次触发，整体时间复杂度会从你预期的O(n)退化为O(n²)——每删除一个元素，后续所有字符都要向前移动一位，这是导致54ms耗时的主要原因。

次要耗时点：额外的字符串复制与反转 #

• 创建 string check = s 保存处理后的字符串，会产生一次O(n)的内存拷贝开销。
• 调用 reverse(s.begin(),s.end()) 后再做字符串比较，多了一次O(n)的反转操作，完全可以通过双指针直接判断回文，省去这两步的冗余开销。

其他可优化细节 #

• 用 while(s[n] != '\0') 遍历C++ string并不严谨，string的长度应该用 s.size() 判断，虽然多数场景能运行，但不符合标准用法，可能在边界case出问题。
• transform 转小写的操作是O(n)，这部分没问题，但可以和过滤操作合并，减少一次遍历。

优化后的示例代码 #

class Solution {
public:
    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--;
            }
            // 转小写后比较
            if (tolower(s[left]) != tolower(s[right])) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

这个版本采用双指针法，仅需一次遍历，无需修改原字符串，也没有额外的拷贝和反转操作，时间复杂度严格为O(n)，空间复杂度O(1)，能大幅降低运行耗时。

内容的提问来源于stack exchange，提问作者Agrim Gusain