滑动窗口

滑动窗口是数组/字符串问题中常用的抽象概念。

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

暴力法

如果使用暴力法，检查所有的子字符串，则时间复杂度为O(n^3)，耗费时间过多。暴力法会反复检查一个字符串是否含有重复的字符，浪费时间。

滑动窗口

窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即 [i, j）（左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。
-例:[i, j）向右滑动1个元素，则它将变为[i+1, j+1)
回到我们的问题，我们使用 HashSet 将字符存储在当前窗口 [i, j)（最初 j = i）中。 然后我们向右侧滑动索引 j，如果它不在 HashSet 中，我们会继续滑动 j。直到 s[j] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 i 开头。如果我们对所有的 i 这样做，就可以得到答案。

优化版的滑动窗口

上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。

• 也就是说，如果 j 对应的字符与[i, j-1]重复，则不再让 i++，而是直接跳过[i, j],令 i=j+1;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0, n = s.length();

        //字符对应的索引为下一次不重复的位置，即下一位置
        //例：j这个地方与前面重复了，则下一次不重复的位置为j+1
        //声明HashMap，形成字符到索引的映射
        Map<Character, Integer> map = new HashMap<>();

        for(int j = 0, i = 0; j < n; j++){
            //如果map中有s[j],则更新i
            if(map.containsKey(s.charAt(j))){
                i = Math.max(map.get(s.charAt(j)), i);
            }

            //更新ans
            ans = Math.max(ans, j-i+1);

            //将s[j]和它到索引的映射(下一个不重复的位置）加入map
            //若是已经重复，则是更新索引，更新为下一次不重复的位置
            map.put(s.charAt(j), j+1);
        }
        return ans;
    }
}