【top】3. 无重复字符的最长子串

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

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

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
    请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解释下： 子串是一段连续的字符。 子序列不是，
重点来了：

这个题目只是需要找到最大长度，而不是要找出对应的字符串。

这个最大长度一直都在变化中，是一直都在比较。

      max 是一直都在变化中的，我们只是保存最大的而已。
     
      使用2个指针，和滑动窗口
      1：fast slow 指针，一开始都指向0。如果没有重复的，那fast 指针就向后移动一位
      2：使用map来判断当前元素是否已经存在，
      3：如果当fast 遇到有重复的数据了，例如现在fast在下标10。slow在下标5。当fast移动到下标11的时候，发现11和5重复了（也就是fast和slow对应的值一样了），那么就移动slow指针，
      将它移动到上一次出现位置的下一个位置，也就是移动slow 到 map.get(slow)+1 的位置上。 因为5-10是不重复的，5和11重复，那么6-11 就是不重复的数据。
      max=fast-slow +1  。因为这个题目是一直都在遍历中，所以每次都要用max来比较，
      所有max=Math.max(max,slow-fast+1);
      如果数据是 abca 当a再加入进去的时候，上一次指向a是0 这次应该移动到1 有效的字符串应该是bca  此时左指针应该是 get(b)+1=1
     如果数据是 abba 当b再进去的时候，此时 上一次指向b的是1 这次应该是移动到2。字段变为了b  当a 再加上去的时候，发现又出现了重复，第一次a是0 现在a是3
     那么按照道理 slow 要从2变为0+1 到1 了，就变成了会退。相当于慢指针往后走了，实际上应该不变，最后字段是ba 才对。
     为了处理问题。
     我们每次获取slow=map.get(重复字符)+1 都要与当前的slow 对比，
     例如 abba 第一次b 重复了 slow =map.get(b)+1=2  此时的max=2-1+1=2
     第二次a 重复了 按照逻辑就是slow=map.get(a)+1=0+1=1 但是上一次slow 已经变成了2 如果回退，那字段就是 bba了。本身就重复了，所以我们需要对slow进行比较，
    slow=Math.max(slow,map.get(重复字符)+1); 这次slow就还是2，此时max=2-2+1=1 因为max是一直在变化，所以max=2 字段变为了ba
    解决了abba的问题后，每一次遍历字符的时候，都应该更新下 当前字符 以及他的下标。
    更新的重点在于下标，主要是因为只有通过下标定位，你才能知道上一次重复字段的下标是多少

    public int lengthOfLongestSubstring3(String s) {
        int max=0;
        int len=s.length();
        int left=0;
        Map<Character,Integer> map=new HashMap<>(len);
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if(map.containsKey(c)){
                left=Math.max(left,map.get(c)+1);
            }
            map.put(c,i);
            max=Math.max(max,i-left+1);
        }
        return max;
    }