这段代码的时间复杂度是多少？我很困惑

Question

所以我正在解决 leetcode“有效回文”问题，我不确定我的代码的时间复杂度是多少，我认为它是 O(n^2) 但我不太确定，所以我使用 chatgpt 来确认，它一直说它是 O(n)。显然内部 while 循环持续运行。

出于某种原因，我无法理解这个问题。欢迎任何解释。谢谢！

这是我的代码：

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

Answer 1

内部 while 循环仅用于跳过空格或标点符号。 让我们运行一个带有回文 'g; 的示例；阿格'

i = 0，j = 5 两个内部 while 循环都会被跳过，因为索引 0 和 5 处的字符都是字母 因为两者都等于 'g' 我们也跳过 if

i = 1，j = 4 现在第一个内部 while 循环被触发，因为索引 1 处的字符不是字母或数字。

i = 2，j = 4 我们仍然处于内部 while 循环中，索引 2 处的字符不再是字母或数字

i = 3，j = 4 现在第一个内部 while 循环为 false，因为索引 3 处的字符是一个字母。 第二个内部 while 循环被跳过，因为索引 4 处的字符是字母

i = 4，j = 3 现在外部 while 循环为 false，因为 i > j。 因此，返回true，并且它是一个有效的回文。

复杂度为 O(n)，因为每个索引只查看一次。

Answer 2

对我来说，它看起来像 O(n)，其中

n

是

s

的长度。

在

while(i < j)

的每次迭代中，

i

的值将至少增加1，而

j

的值将至少减少1。当遇到非字母数字字符时，

的值将增加。 i

、

j

或两者都将被更改多个。比较次数

(s.charAt(i) != s.charAt(j))

永远不会超过

n/1

。所以，O(n)。