1. 题目
给定一个字符串，找出其中不含重复字符的最长子串的长度。
示例1：
输入："abcabcbb"
输出：3
解释：因为无重复字符的最长子串是："abc"，所以其长度为3
示例2：
输入："bbbbb"
输出：1
解释：因为无重复字符的最长子串是："b"，所以其长度为1
示例3：
输入："pwwkew"
输出：3
解释：因为无重复字符的最长子串是："wke"或"kew"，所以其长度为3
注意：必须是子串的长度，子串是连续的字符，中间不能跳跃字符，如"pwke"是一个子系列，不是子串。
2. 解题思路
2.1 思路一：滑动窗口
窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即[i, j)（左闭，右开），而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。
例如：
我们将[i, j)向右滑动1个元素，则它将变为[i+1, j+1)（左闭，右开）
用HashSet存储当前处于窗口[i, j)(最初 j = i)中的字符，然后我们向右滑动索引j，如果它不在HashSet中，我们会继续滑动j，直到s[j]已经存在于HashSet中，此时没有重复的最长子字符串将会以索引i开头
用
HashSet存放当前处于滑动窗口中的字符，初始HashSet为空。
窗口的左边i不动，右边j向右滑动，依次遍历字符：j为指向字符的索引。
当j = 0时，遍历字符p，加入HashSet -- [p]，则目前无重复字符的最大子串长度maxSubLength = 1
当j = 1时，遍历字符w，加入HashSet -- [p, w]，则maxSubLength = 2滑动窗口1.png当j = 2时，遍历字符w，此时HashSet中已包含重复字符w，
则窗口的左边i向右滑，右边j不动，HashSet依次删除索引i所指向的字符，直到HashSet不再包含该字符w，
然后重新将遍历字符w加入HashSet中，启动窗口j继续右滑。滑动窗口2.png窗口的左边
i不动，右边j继续向右滑动，依次遍历字符：j为指向字符的索引
当j = 3时，遍历字符k，加入HashSet -- [w k]
当j = 4时，遍历字符e，加入HashSet -- [w k e]，则此时maxSubLength = 3
滑动窗口3.png当j = 5时，遍历字符w，此时HashSet中已包含重复字符w，
则窗口的左边i向右滑，右边j不动，HashSet依次删除索引i所指向的字符，直到HashSet不再包含该字符w，
然后重新将遍历字符w加入HashSet中，启动窗口j右滑。
结束，则maxSubLength = 3滑动窗口4.png
代码实现：
public static int lengthOfLongestSubstring(String s) {
if (s == null || "".equals(s)) {
return 0;
}
int n = s.length();
Set<Character> set = new HashSet<>();
int maxLength = 0;
int i = 0;
int j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
maxLength = Math.max(j - i, maxLength);
} else {
set.remove(s.charAt(i++));
}
}
return maxLength;
}
2.2 思路二：优化的滑动窗口
针对上述的滑动窗口方法，不使用集合来判断一个字符是否存在，而定义字符到索引的映射map。
当找到重复字符时，可以立即跳过该窗口。
如果在[i, j)范围内有与s[j]重复的字符，索引为j'，即[i, ... j', ... j)，
我们不需要逐渐增加i，可以直接跳过[i, j']范围内的所有元素，并将i变为j' + 1
举例：
s = "pwwkew"，当 j = 2时，窗口[0, 2)范围内有与s[2]重复的字符w，索引为1(j' = 1)，我们可以直接跳过[0, 1]范围内的所有元素，将i变为2(j' + 1)
代码实现：
public static int lengthOfLongestSubstring(String s) {
if (s == null || "".equals(s)) {
return 0;
}
int n = s.length();
Map<Character, Integer> map = new HashMap<>(16);
int maxLength = 0;
for (int i = 0,j = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
maxLength = Math.max(maxLength, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return maxLength;
}
2.3 思路三：使用列表List存储不重复字符
依次遍历字符串 s 中的每次字符，若不是重复字符，加入一个列表list中，若是重复字符，则删除列表list中该重复字符以及前面的所有字符，然后再将该重复字符加入此列表list中。
在遍历的过程中统计出列表list中存储的最大字符个数，即为字符串 s 中不含重复字符的最长子串的长度。
代码实现
public static int lengthOfLongestSubstring(String s) {
if (s == null || "".equals(s)) {
return 0;
}
List<Character> list = new ArrayList<>();
int n = s.length();
int maxLength = 0;
for (int i = 0; i < n; i++) {
int index = list.indexOf(s.charAt(i));
if (index == -1) {
list.add(s.charAt(i));
maxLength = Math.max(list.size(), maxLength);
} else {
for (int j = index; j >= 0; j--) {
list.remove(j);
}
list.add(s.charAt(i));
}
}
return maxLength;
}
