java - 最长子串，超过时间限制java

Question

给定一个字符串，找出最长的没有重复字符的子串的长度。例如，“abcabcbb”的最长不重复字母子串是“abc”，长度为3。“bbbbb”的最长子串是“b”，长度为1。

public static int lengthOfLongestSubstring(String s) {
    if (s.length()==0)
        return 0;
    int maxlen = 1;

    HashMap<Character, ArrayList<Integer>> check = new HashMap<Character,ArrayList<Integer>>();
    for (int i = 0; i < s.length(); i++) {
        for (int j = i; j < s.length(); j++) {
            if (!check.containsKey(s.charAt(j))) {
                ArrayList<Integer> value= new ArrayList<>();
                value.add(j);
                check.put(s.charAt(j), value);
            }
            else {
                maxlen = Math.max(j - i, maxlen);
                ArrayList<Integer> temp = check.get(s.charAt(j));
                i=temp.get(temp.size()-1);  
              // get the last index(biggest index) of the key value
                check.clear();
                break;
            }
            if(j==s.length()-1) {
                maxlen = Math.max(j - i + 1, maxlen);
            }

        }
    }
    return maxlen;
  }
}

最后一次测试长可重复字符串，超出了时间限制。不知道怎么优化。求改进，谢谢

Answer 1

这是一个相当简单的解决方案，应该比您的解决方案更快:

public static int longestNonRepeating(final String s) {
    final Set<Character> unique = new HashSet<>();
    int max = 0;
    for (int i = 0; i < s.length(); ++i) {
        final char c = s.charAt(i);
        if (!unique.add(c)) {
            for (int j = i - unique.size(); j < i; ++j) {
                if (s.charAt(j) != c) {
                    unique.remove(s.charAt(j));
                } else {
                    break;
                }
            }
        }
        max = Math.max(max, unique.size());
    }
    return max;
}

这是如何工作的？

我们遍历 String 并将字符添加到 Set。如果我们添加的字符已经包含在 Set 中，那么我们就知道在当前子字符串中有一个重复字符。

在这种情况下，我们从当前子串的开头开始(其长度必须与 unique 的大小相同)。如果我们找到的字符不是我们找到的重复字符，则重复字符必须在更远的地方，我们会继续搜索。一旦找到重复项，我们就可以停止搜索。

将过程可视化:

a  b  c  a  b  c
0  1  2  3  4  5
^
|
i

在我们独特的集合中有a。

a  b  c  a  b  c
0  1  2  3  4  5
   ^
   |
   i

我们的唯一集合中有a,b。

a  b  c  a  b  c
0  1  2  3  4  5
      ^
      |
      i

在我们独特的集合中有a,b,c。

a  b  c  a  b  c
0  1  2  3  4  5
^        ^
|        |
j        i

我们尝试添加a到唯一的Set，它是一个副本。从唯一子字符串的开头，尝试找到一个 a。幸运的是这是在 0，我们不需要从 unique 中删除任何东西。

a  b  c  a  b  c
0  1  2  3  4  5
   ^        ^
   |        |
   j        i

我们尝试添加 b 到唯一的Set，它是一个副本。从唯一子字符串的开头，尝试找到一个 b。幸运的是，这是在 1，我们不需要从 unique 中删除任何内容。

a  b  c  a  b  c
0  1  2  3  4  5
      ^        ^
      |        |
      j        i

我们尝试添加 c 到唯一的Set，它是一个副本。从唯一子字符串的开头，尝试找到一个 c。幸运的是，这是在 1，我们不需要从 unique 中删除任何内容。

我们完成了。最长的唯一子串是 3。