这里主要是用到一个移动窗口的概念。窗口移动要解决的问题则是
如果当前的字符已经重复了。那么接下来我的窗口的起始位置应该放在哪。
也就是说，我们需要记录一个字符和他重复时下一个起始位置的对应关系。
一个例子
这里用一个 nextBeginPos[128]来记录对应字符重复时的下一个起始位置。
每次算当前窗口长度的时候用 end - begin + 1, 然后和当前的 maxLength 比较。如果比他大，则用 end - begin + 1;
LeetCode3无重复最长子串.jpg
image.png
public class LongestSubString {
public static int longest(String s) {
int maxLength = 0;
int[] nextBeginPos = new int[128];
for (int begin = 0, end = 0; end < s.length(); end++) {
begin = nextBeginPos[s.charAt(end)] > begin ? nextBeginPos[s.charAt(end)] : begin;
maxLength = maxLength > end - begin + 1 ? maxLength : end - begin + 1;
nextBeginPos[s.charAt(end)] = end + 1;
}
return maxLength;
}
public static void main(String[] args ) {
System.out.println(longest("abcabcbb"));
}
}
