题目
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 示例 4:
输入: s = "" 输出: 0
思路
这道题难度是中等，我觉得挺难的，如果没接触过，估计很难在较低的算法复杂度下做出来，
主要考察滑动窗口算法
听起来“滑动窗口”很牛逼，其实就是类似双指针，
在两个指针之内的是符合条件的元素
如果遇到不符合条件得元素则两个指针向右移动，剔除最左边元素
比如abc是一个窗口，当再遇到a时，窗口内变成bca
代码实现如下，算法复杂度为O(n2)
public static int lengthOfLongestSubstring2(String s) { int result = 0; if (s.length() == 0) { return result; } int len = 0; int start = 0; for (int end = 0; end < s.length(); end++) { char cur = s.charAt(end); //判断前面循环过的是否包含当前的字符 for (int i = 0; i < end; i++) { //如果包含，跳过第一次出现的位置，从之后位置计算 if (s.charAt(i) == cur) { start = i + 1; len = end - start; break; } } result = Math.max(result, ++len); } return result; }
优化
上面实现的方案，在判断当前字符是否出现过时每次都是从前面遍历过数据中再次遍历
这种效率肯定不高，所以考虑通过hash表进行优化
public static int lengthOfLongestSubstring(String s) { int result = 0; if (s.length() == 0) { return result; } // 用map保存元素的位置，如果下一个字符在map中出现过 // 证明窗口需要左移，窗口左指针为map中重复元素的下一个 Map<Character, Integer> char2index = new HashMap<>(); //start,end左右指针组成滑动窗口 for (int start = 0, end = 0; end < s.length(); end++) { char element = s.charAt(end); if (char2index.containsKey(element)) { //char2index.get()的地方进行+1操作 ，此处是重点 start = Math.max(char2index.get(element) + 1, start); } result = Math.max(result, end - start + 1); char2index.put(element, end); } return result; }
小结
滑动窗口的相关的题目还是很有规律可循的，明天争取抽个时间，对滑动窗口的题目做个总结与归纳，把相关题目梳理一遍。
