LeetCode 中无重复字符的最长子串

Question

给定一个字符串 s，求最长不包含重复字符的子串的长度。

输入：s =“abcabcbb” 输出：3 解释：答案是“abc”，长度为3。

public static int lengthOfLongestSubstring(String s) {
    String str = "";
    int max = 0;
    for(int i=0; i<s.length(); i++){
        if(str.contains(Character.toString(s.charAt(i)))){
            if(max<str.length()){
                max = str.length();
            }
            i = str.indexOf(s.charAt(i));
            str = "";
        }
        else{
            str += s.charAt(i);
        }
    }
    if(max<str.length()){
        max = str.length();
    }
    System.out.println(str);
    return max;
}

我尝试遍历 String s 中的每个字符，如果它不在 String str("substring of s") 中，我将其添加到 str 中。如果字符已经在 str 中，那么我将 str 的长度保存在 max 中（如果 max

如果输入是：“abcbdef” 第一个 str 是：“abc”。然后，因为 'b' 不断重复，所以该子字符串结束，i=1（第一个 b 的索引），在 i++ i=2(c) 和 str="" 之后；从这里开始我的新子字符串。 第二个str是：“cbdef” 最大值 = 5

但是如果输入是：“abcabcbb”，则不起作用。这是为什么？

Answer 1

您正在运行无限循环，因为

i

未正确重置。一旦找到重复的字符，您需要从上一个过程开始处的下一个字符重新开始整个过程。例如，如果字符串是

abcaeb

，则第一个搜索以

a

开头。一旦找到

a

，当前最大值将为

3

，字符串将为

abc

。然后您需要从

b

开始重复该过程。然后就会找到

bcae

。

因此使用嵌套循环如下：

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

然后注释掉

i = str.indexOf(s.charAt(i));

这是修改后的方法。

public static int lengthOfLongestSubstring(String s) {
     String str = "";
     int max = 0;
     for (int restart = 0; restart < s.length(); restart++) {
         for (int i = restart; i < s.length(); i++) {
             if (str.contains(Character.toString(s.charAt(i)))) {
                 if (max < str.length()) {
                     max = str.length();
                 }
                 // i = str.indexOf(s.charAt(i));
                 str = "";
             } else {
                 str += s.charAt(i);
             }
         }
         if (max < str.length()) {
             max = str.length();
         }
     }
     
     
     return max;
 }