求解：我的有效回文判断代码时间复杂度为何是O(n)？

你写的这段有效回文判断代码，时间复杂度确实是O(n)，而非O(n²)，核心原因在于内层的while循环并非每次外层循环都执行O(n)次，而是所有内层循环的总执行次数加起来不超过O(n)，具体解释如下：

你的代码 #

class Solution {
    public boolean isPalindrome(String s) {

        int i = 0; 
        int j = s.length()-1;

        s = s.toLowerCase();

        while(i < j) {

            while(i < j && !Character.isLetterOrDigit(s.charAt(i))){
                i++;
            }

            while(i < j && !Character.isLetterOrDigit(s.charAt(j))){
                j--;
            }

            if(s.charAt(i) != s.charAt(j)){
                return false;
            }

            i++;
            j--;

        }

        return true;
    }
}

时间复杂度分析 #

• 核心逻辑：指针单向移动，无重复遍历
  变量i只会从左向右移动（初始0，最终最多到n-1），变量j只会从右向左移动（初始n-1，最终最少到0），两个指针都不会回头。
• 内层循环的总执行次数有限
  两个内层while循环的作用是跳过非字母数字字符，每次执行都会让i或j向中间靠近一步，不会重复处理同一个字符。整个过程中，i和j的总移动次数加起来最多是n次（覆盖整个字符串的所有字符）。
• 外层循环的迭代次数
  外层while循环每次迭代，要么完成一次有效字符的比较后让i和j各移动一步，要么通过内层循环让其中一个指针移动一步，外层循环的总迭代次数最多是n/2次，但每次迭代对应的操作（包括内层循环）都是常数级的总消耗，不会出现外层循环n次、内层循环每次n次的情况。

简单来说，整个算法中每个字符最多被访问一次（要么被跳过，要么被比较），总操作次数和字符串长度n成正比，因此时间复杂度是O(n)，而非O(n²)。

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