Java中的String方法是否在O(1)时间内运行？

Question

这是我的代码,用于查找最长子字符串的长度而不重复字符.这段代码是否在O(n)时间内运行？或者它是否在O(n ^ 2)时间内运行？我不确定String方法是在O(n)时间还是O(1)时间运行.

测试用例包括:"pwwkewo"返回4,因为"kewo"是字符串中具有唯一字符的最长子字符串.

public int lengthOfLongestSubstring(String s) {

    int maxLength = 0;
    String sub = "";

    for(int i=0; i<s.length(); i++) {

         //add that char to the sub string
         sub = sub + s.charAt(i);

        //if we find a char in our string
        if(sub.indexOf(s.charAt(i)) != -1) {

           //drop any replicated indexes before it
            sub = sub.substring(sub.indexOf(s.charAt(i)) + 1);
        }

        if(sub.length() > maxLength) {
            maxLength = sub.length();
        }


    }

    return maxLength;

}

Answer 1

sub.indexOf()可能需要线性时间,因为它可能需要检查所有字符sub.在最坏的情况下,长度sub为O(n)(假设您的输入没有重复字符).

因此,您的总运行时间为O(n ²),因为循环具有n迭代并且在每次迭代中都会调用indexOf().