题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
初始思路
这个题目虽然标注为“简单”，但是我也依然是断断续续利用业余时间做了两三天才通过。看到这个题的第一反应就是用双指针，一个 fast 一个 slow，最后计算两者的差值来求最大值。这可能也是因为我前不久做了好几个链表的题目，其中检测是否有环等题目都是用双指针完成的，所以就“拿着锤子，看什么都是钉子”了。
我的第一反应是 fast 指针一个一个的扫描，然后和slow 指针的值比较，发现重复的，就 slow 指针往前一位。但是实际实现的时候，发现是不对的，因为重复的字符不一定是刚好在 slow 所指向的位置，而是可能是中间某一个位置，比如 abcdefcd，当已扫描字符串为 abcdef 且当前正在扫描的是 c 的时候，按照这个错误的思路，a != c 我们认为还没有重复，但是 c 和第三个位置的 c 已经重复了！
于是为了修正这个问题，我需要一个集合，记录了已经存在的字符，光有 fast 和 slow 是不够的。顺着这个思路，当发现某个字符（上例中的 c ）已经存在与集合中时，我们就知道该更新一下当前的最长子串的长度了，因为再往前就要移除一些重复的字符了。那么这个时候问题来了，要从已扫描的字符串（上例中的 abcdef）中移除多少个头部字符呢？我们需要从头部开始找，一直到找到重复的字符的位置，然后从这个位置开始，它前面的都不用，它后面的重新构建新的集合。构建好新的集合之后，我们继续扫描，于是就有如下勉强通过的代码了（i 其实就是 fast）：
public int lengthOfLongestSubstring(String s) {
// System.out.println(String.format("s.length(): %s", s.length()));
if (s == null) {
return 0;
}
if (s.length() <= 1) {
return s.length();
}
int slow = 0;
int maxL = 0;
Set<Character> existChars = new HashSet<>();
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// System.out.println(String.format("process i: %s, char: %s", i, c));
if (existChars.contains(c)) {
existChars = new HashSet<>();
// 出现重复，需要更新 slow 的位置，更新 maxL, 更新 existChars
if (i - slow > maxL) {
maxL = i - slow;
}
boolean reput = false;
for (int j = slow; j <= i; j++) {
// 更新 existChars
if (reput) {
existChars.add(s.charAt(j));
}
if (!reput && s.charAt(j) == c) {
// j 就是重复的位置
slow = j + 1;
reput = true;
}
}
} else {
existChars.add(c);
}
}
// 最后一次计算
if (s.length() - slow > maxL) {
maxL = s.length() - slow;
}
return maxL;
}升级版本
在看了官方的解题思路之后，才意识到，以上解法中，其实有一些步骤是可以进一步优化的。比如每次遇到重复的字符之后，我就清空了已经存在的字符集合，然后在依次判断是否重复，重新装回集合。其实这个是有点多费手续了，仔细想想，其实我就是想把重复的丢掉而已，没必要整体清空，一个一个的去重重复的就可以：
public int lengthOfLongestSubstring(String s) {
if (s == null) {
return 0;
}
if (s.length() <= 1) {
return s.length();
}
int slow = 0;
int fast = 0;
int maxL = 0;
Set<Character> existChars = new HashSet<>();
while(slow < s.length() && fast < s.length()) {
char c = s.charAt(fast);
if (existChars.contains(c)) {
existChars.remove(s.charAt(slow));
maxL = Math.max(maxL, fast - slow);
slow++;
} else {
existChars.add(c);
fast++;
}
}
maxL = Math.max(maxL, fast - slow);
return maxL;
}进一步优化
以上的升级版本还有一个地方可以优化，就是每次遇到有重复字符出现时，都要一个一个的剔除重复的，如果我们在记录字符的同时记录了字符的位置，那么 slow 就可以之下指向最终应该到的位置，而不用一步一步的过去：
public int lengthOfLongestSubstring(String s) {
if (s == null) {
return 0;
}
if (s.length() <= 1) {
return s.length();
}
int slow = 0;
int fast = 0;
int maxL = 0;
Map<Character, Integer> existCharLocationMap = new HashMap<>();
while(slow < s.length() && fast < s.length()) {
char c = s.charAt(fast);
if (existCharLocationMap.keySet().contains(c) && existCharLocationMap.get(c) >= slow) {
maxL = Math.max(maxL, fast - slow);
slow = existCharLocationMap.get(c) + 1;
existCharLocationMap.remove(c);
} else {
existCharLocationMap.put(c, fast);
fast++;
}
}
maxL = Math.max(maxL, fast - slow);
return maxL;
}其实就是滑动窗口
上面的两种解法，就是处理字符串问题常用的滑动窗口方法，前一个是尾部一次一格的滑动窗口，后一个是一次一步到位的。
题目描述
初始思路
这个题目虽然标注为“简单”，但是我也依然是断断续续利用业余时间做了两三天才通过。看到这个题的第一反应就是用双指针，一个
fast一个slow，最后计算两者的差值来求最大值。这可能也是因为我前不久做了好几个链表的题目，其中检测是否有环等题目都是用双指针完成的，所以就“拿着锤子，看什么都是钉子”了。我的第一反应是
fast指针一个一个的扫描，然后和slow指针的值比较，发现重复的，就slow指针往前一位。但是实际实现的时候，发现是不对的，因为重复的字符不一定是刚好在slow所指向的位置，而是可能是中间某一个位置，比如abcdefcd，当已扫描字符串为abcdef且当前正在扫描的是c的时候，按照这个错误的思路，a != c我们认为还没有重复，但是c和第三个位置的c已经重复了！于是为了修正这个问题，我需要一个集合，记录了已经存在的字符，光有
fast和slow是不够的。顺着这个思路，当发现某个字符（上例中的c）已经存在与集合中时，我们就知道该更新一下当前的最长子串的长度了，因为再往前就要移除一些重复的字符了。那么这个时候问题来了，要从已扫描的字符串（上例中的abcdef）中移除多少个头部字符呢？我们需要从头部开始找，一直到找到重复的字符的位置，然后从这个位置开始，它前面的都不用，它后面的重新构建新的集合。构建好新的集合之后，我们继续扫描，于是就有如下勉强通过的代码了（i其实就是fast）：升级版本
在看了官方的解题思路之后，才意识到，以上解法中，其实有一些步骤是可以进一步优化的。比如每次遇到重复的字符之后，我就清空了已经存在的字符集合，然后在依次判断是否重复，重新装回集合。其实这个是有点多费手续了，仔细想想，其实我就是想把重复的丢掉而已，没必要整体清空，一个一个的去重重复的就可以：
进一步优化
以上的升级版本还有一个地方可以优化，就是每次遇到有重复字符出现时，都要一个一个的剔除重复的，如果我们在记录字符的同时记录了字符的位置，那么
slow就可以之下指向最终应该到的位置，而不用一步一步的过去：其实就是滑动窗口
上面的两种解法，就是处理字符串问题常用的滑动窗口方法，前一个是尾部一次一格的滑动窗口，后一个是一次一步到位的。