算法思想

这道题是很经典的一道题，所以一定要弄懂，

双指针算法：声明两个指针，i指针循环s字符串，j指针代表前j个字符有重复元素，所以取值不能小于j，要取j之后

问题

1：为什么下面代码要 + 1

j = Math.max(j, map.get(s.charAt(i)) + 1);

+1是为了去除重复的元素

2：为什么 j要取最大值

j代表前j个字符有重复元素，所以要从第j个字符开始数，

举例：c h b m m c g
0 1 2 3 4 5 6
当j = 4时，i等于5，出现了重复的元素c

如果让j = map.get(s.charAt(i), j = 1,但是i - j之间出现了重复的元素mm,所以j要从4开始数,才能避免重复

java 代码

class Solution {
    public int longestSubstringWithoutDuplication(String s) {
        Map<Character, Integer> map = new HashMap<>();   // 记录 字符索引的位置
        int res = 0;
        for(int i = 0, j = 0; i < s.length(); i ++)
        {
            if(map.containsKey(s.charAt(i)))            // 说明出现了重复的
                j = Math.max(j, map.get(s.charAt(i)) + 1);
            map.put(s.charAt(i), i);                    // 会更新重复元素的位置
            res = Math.max(res, i - j + 1);
        }
        return res;
    }
}