滑动窗口

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> window = new HashMap<Character,Integer>();
        int left = 0;
        int right = 0;
        int max = 0;
        //判断窗口的右边界是否到达字符串的末尾
        while(right < s.length()){
            //取出right指针对应的元素
            Character r = s.charAt(right);
            right++;

            //对窗口内数据进行一系列更新
            if(window.containsKey(r)){
                window.put(r,window.get(r)+1);
            }else{
                window.put(r,1);
            }

            //缩小窗口的条件需要自行指定
            while(window.get(r) > 1){
                //取出left指针对应的元素
                Character l = s.charAt(left);
                left++;
                //窗口缩小后进行的处理
                window.put(l,window.get(l)-1);
            }
            //计算逻辑写在这里
            max = Math.max(right-left,max);
        }
        return max;
    }
}

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int left = 0;
        int right = 0;
        int n = s2.length();
        int valid = 0;

        Map<Character,Integer> goal = new HashMap<Character,Integer>();
        Map<Character,Integer> windows = new HashMap<Character,Integer>();

        //合法性判断
        if(s1.length() > s2.length()){
             return false;
        }

        //扫描s1将s1中串的信息保存 使用HashMap要比数组啰嗦的多
        for(int i=0;i<s1.length();i++){
            Character c = s1.charAt(i);
            if(goal.containsKey(c)){
                goal.put(c,goal.get(c)+1);
            }else{
                goal.put(c,1);
            }
        }

        // 滑动窗口框架
        while(right < n){
            Character c = s2.charAt(right);
            right++;

            //将当前元素放入窗口
            if(goal.containsKey(c)){
                if(windows.containsKey(c)){
                    windows.put(c,windows.get(c)+1);
                }else{
                    windows.put(c,1);
            }
                //判断增加此元素后 是否满足了排列组合中对该字母数量的要求
                if(windows.get(c).equals(goal.get(c))){
                    valid++;
                }
            }

            // 当长度与到达或者超过s1时 执行判断
            while(right - left >= s1.length()){
                //若当前所有元素已经满足了排列组合中对该字母数量的所有要求
                //返回匹配成功
                if(valid == goal.size()){
                    return true;
                }

                //否则 移动左指针对窗口进行收缩
                Character d = s2.charAt(left);
                left++;
                
                //移除左侧元素
                if(goal.containsKey(d)){
                    //判断减去该元素是否会导致某字母不再满足子串字母的匹配需求
                    if(windows.get(d).equals(goal.get(d)))
                        valid--;
                    windows.put(d,windows.get(d)-1);
                }
            }
            
        }
        //执行至最后还没有结果 return false
        return false;
    }
}