用哈希表优化子串的遍历与跳转，实现剪枝。

3. 题目链接-来源：力扣（LeetCode） （中等）

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

####思路：
这是一个「滑动窗口」问题。基本思路就是用一个开头下标start和一个结尾下标i来标记当前处理的区域。
接下来考虑怎么判断重复问题，最直观的想法就是查找，最快的查找就是哈希表（复杂度O(1)）。那么就考虑维护一个哈希表isRepeated，存储当前子串中的字符，每次i扫过新的字符就查表，如果存在key则说明重复，不存在则将其加入；然后start前进，直到找到重复字符所在的下标，前进的同时逐个删去经过的字符在表中的记录。
进一步优化：
考虑最坏情况，可能存在”abcdefgg”这样的字符串，start指向’a’，当i扫过第2个’g’的时候，哈希表查到冲突，但是start需要依次扫过abcdefg才能确定冲突的位置，效率太低。
优化方案：用HashMap而不是HashSet，key仍然是字符，Value则为该字符对应的下标。这样检测到重复以后，start只要指向Value的下一位即可，不用再浪费时间遍历之前没有出现重复的子串。

时间复杂度：遍历了一遍长度为n的字符串，O(n)
空间复杂度：维护了一个n个元素的哈希表，O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> isRepeated = new HashMap<>();
        int n = s.length(), maxLength = 0;
        for(int i = 0, start = 0; i < n; i++) {
            char newChar = s.charAt(i);
            if(isRepeated.containsKey(newChar)) {
                int repeatBreak = isRepeated.get(newChar);
                start = Integer.max(start, repeatBreak + 1);   
            }
            isRepeated.put(newChar, i);
            maxLength = Integer.max(maxLength, i - start + 1);
        }
        
        return maxLength;
    }
}