LC03-无重复字符的最长子串

链接

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

准备知识

什么是子串、什么是子序列？
最大的问题是子串连续，子序列不连续，涉及到子串的问题，要么就是动态规划，要么就是滑动窗口

双指针模板

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

思路

1：不管三七二十一滑动窗口模板安排上
2：使用map 缓存遍历过的信息
3：思考什么场景出发j ++ ,当然是查Map出现重复的key，即map的value>1
4：移出之后Map缓存的value减1，map.getOrDefault 是指没有就设置0，有就取值追加
5：比较res 大小，请形成规范，所有有返回的请使用res（result)好吗？

代码

  public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> map = new HashMap<Character,Integer>();
        int res = 0;
        //i在前，j在后
        for(int i = 0,j = 0;i < s.length();i ++)
        {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);

            //判断i位置的元素是否有重复，有重复j向前走
            while(j < i && map.get(s.charAt(i)) > 1)
            {
                map.put(s.charAt(j), map.get(s.charAt(j)) - 1);
                j ++;
            }
            res = Math.max(res, i - j + 1);
        } 
        return res;

    }
如果getOrDefault 不知道也可以这样写咯
 //滑动窗口
    public int lengthOfLongestSubstring(String s) {
       HashMap<Character,Integer> cache = new HashMap<>();
       int res = 0;
       for(int i = 0, j = 0; i < s.length(); i ++){
           if(cache.containsKey(s.charAt(i)) || cache.get(s.charAt(i)) != null){
               cache.put(s.charAt(i), cache.get(s.charAt(i)) + 1);
           }
           else{
               cache.put(s.charAt(i),1);
           }

           //cache.put(s.charAt(i), cache.getOrDefault(s.charAt(i), 0) + 1);

           while(j < i && cache.get(s.charAt(i)) > 1){
               cache.put(s.charAt(j), cache.get(s.charAt(j)) - 1);
               j++;
           }
           res = Math.max(res,i - j + 1);
       }
       return res;

    }