前文算法笔记

滑动窗口解决字串问题

首先滑动窗口是有模块的，在套模版之前需要明白以下四点

1.right指针扩大窗口，即加入字符时，应该更新哪些数据
什么条件下，窗口应该暂停扩大，开始移动left缩小窗口
当移动left缩小窗口，移除字符时更新哪些数据
我们需要的结果时在扩大窗口还是缩小窗口时进行更新

76.最小覆盖字串

我们有一个windows的滑动窗口，通过控制left和right指针的移动，最开始我们用一个need集合存放t字串中的每个字符，valid代表字串个数
具体操作就是right往右走，然后呢直到遇到valid满足，这个时候需要缩减窗口了，缩减窗口的时候要记录其结果

class Solution {
    public String minWindow(String s, String t) {
        Map<Character,Integer>need = new HashMap<>();
        Map<Character,Integer>windows = new HashMap<>();
        int left = 0;
        int right = 0;
        int start = 0;
        int valid = 0;
        int len = Integer.MAX_VALUE;
        for(char c:t.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        while(right < s.length()){
            char c = s.charAt(right);
            right++;
            if(need.containsKey(c)){
                windows.put(c,windows.getOrDefault(c,0)+1);
                if(windows.get(c).equals(need.get(c))){
                    valid++;//代表字符串中有和字串一样的字符
                }
            }
            //判断左侧窗口是否要进行收缩
            while(valid==need.size()){
                if(right-left < len){//更新长度，只记录最短的
                    start = left;
                    len = right-left;
                }
                char d = s.charAt(left);
                left++;
                if(need.containsKey(d)){
                    if(need.get(d).equals(windows.get(d))){
                        valid--;
                    }
                windows.put(d,windows.getOrDefault(d,0)-1);//代表windows中含字串的字符多一些
                }
            }   
        }
        len = len==Integer.MAX_VALUE? 0:len;
            return s.substring(start,start+len);
    }
}

567.字符串的排列

这题同样也是字串问题，一看就是利用滑动窗口，与上一题不一样的在于这里是排列的字串，也就是我们要判断的就是windows中是否含有need，且它两长度要一致，代表着我们的这题的范围更小了
所谓的窗口伸长或者缩短，都是根据need.containsKey(d)，只有包含了才进行窗口的改变

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int sz = s2.length();
        Map<Character,Integer>need = new HashMap<>();
        Map<Character,Integer>window = new HashMap<>();
        for(char c : s1.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        } 
        int left =0;
        int right = 0;
        int valid = 0;
        while(right<sz){
            char c = s2.charAt(right);
            right++;
            if(need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if(window.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            //判断是否需要收缩
            while(valid==need.size()){
                //字串包含s1的全部字符 且长度相等 即满足了题意
                if(right-left == s1.length()){
                    return true;
                }
                //要移除的字符
                char d = s2.charAt(left);
                left++;
                //此时也要更新window的值
                if(need.containsKey(d)){
                    if(window.get(d).equals(need.get(d))){
                        valid--;
                    }
                    window.put(d,window.getOrDefault(d,0)-1);
                }
            }
        }
        return false;
    }
}

458.找到字符串中的字母异位词

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        HashMap<Character,Integer>windows = new HashMap<>();
        HashMap<Character,Integer>need = new HashMap<>();
        int left = 0;
        int right = 0;
        int valid = 0;
        List<Integer>list = new ArrayList<>();
        for(char c : p.toCharArray()){
            need.put(c,need.getOrDefault(c,0)+1);
        }
        while(right < s.length()){
            char c = s.charAt(right);
            right++;
            if(need.containsKey(c)){
                windows.put(c,windows.getOrDefault(c,0)+1);
                if(windows.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            while(valid==need.size()){
                if(right - left == p.length()){
                    list.add(left);//和判断不一样的是，我们只需要将其left加到List即可
                }
                char d = s.charAt(left);
                left++;
                if(need.containsKey(d)){
                    if(windows.get(d).equals(need.get(d))){
                        valid--;
                    }
                    windows.put(d,windows.getOrDefault(d,0)-1);
                }
            }
        }
            return list;
    }
}

3.无重复字符的最长字串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer>windows = new HashMap<>();
        int left = 0;
        int right = 0;
        int res = 0;
        while(right<s.length()){
            char c = s.charAt(right);
            right++;
            windows.put(c,windows.getOrDefault(c,0)+1);
            //如果windows含当前的代表重复了，需要缩减窗口
            if(windows.containsKey(c)){
                while(windows.get(c)>1){
                    char a = s.charAt(left);
                    left++;
                    windows.put(a,windows.getOrDefault(a,0)-1);
                }
                 res = Math.max(res,right-left);
            }
        }
        return res;
    }
}