算法及数据结构系列 - 滑动窗口

系列文章目录

算法及数据结构系列 - 二分查找
算法及数据结构系列 - BFS算法
算法及数据结构系列 - 动态规划
算法及数据结构系列 - 双指针
算法及数据结构系列 - 回溯算法
算法及数据结构系列 - 树

滑动窗口

框架思路

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

经典题型

76. 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = “ADOBECODEBANC”, T = “ABC”
输出: “BANC”
说明：

如果 S 中不存这样的子串，则返回空字符串 “”。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

提示：通过valid记录满足条件的字符数;只关注need中的字符
注意: Integer 类型比较 不能用 == ！！！！, 要用 equals()

class Solution {
    public String minWindow(String s, String t) {
        int left = 0, right = 0;
        Map<Character, Integer> win = new HashMap<Character, Integer>();
        Map<Character, Integer> need = new HashMap<Character, Integer>();
        for(int i = 0; i< t.length(); i++){
            need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
        }
        int valid = 0;
        int start = -1, len = Integer.MAX_VALUE;
        while(right < s.length()){
            char c = s.charAt(right);
            right ++;
            if(need.containsKey(c)){
                win.put(c, win.getOrDefault(c, 0) + 1);
                if(win.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(win.get(d).equals(need.get(d))){
                        valid --;
                    }
                    win.put(d, win.get(d) - 1);
                }
            }
        }
        return start == -1? "":s.substring(start, start + len);
    }
}

567. 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo"  
输出: True  
解释: s2 包含 s1 的排列之一 ("ba").  

示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int left = 0, right = 0;
        int[] win = new int[256];
        int[] need = new int[256];
        int needCharSize = 0;
        for(int i = 0 ; i< s1.length(); i++){
            if (need[s1.charAt(i)] == 0){
                needCharSize++;
            }
            need[s1.charAt(i)] ++;
        }
        int valid = 0;
        while(right < s2.length()){
            char c = s2.charAt(right);
            right++;
            if(need[c] > 0){
                win[c]++;
                if(need[c] == win[c]){
                    valid++;
                }
            }
            while(valid == needCharSize){
                if(right - left == s1.length()){
                    return true;
                }
                char d = s2.charAt(left);
                left++;
                if(need[d] > 0){
                    if(need[d] == win[d]){
                        valid--;
                    }
                    win[d]--;
                }
            }
        }
        return false;
    }
}

438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。

class Solution {
    List<Integer> res = new ArrayList<Integer>();
    public List<Integer> findAnagrams(String s, String p) {
        int left = 0, right = 0;
        int[] win = new int[256];
        int[] need = new int[256];
        int needCharSize = 0;
        for(int i = 0; i< p.length();i++){
            char c = p.charAt(i);
            if(need[c] == 0){
                needCharSize++;
            }
            need[c]++;
        }
        int valid = 0;
        while(right < s.length()){
            char c = s.charAt(right);
            right++;
            if(need[c] > 0){
                win[c] ++;
                if(win[c] == need[c]){
                    valid ++;
                }
            }

            while(valid == needCharSize){
                if(right - left == p.length()){
                    res.add(left);
                }
                char d = s.charAt(left);
                left++;
                if(need[d] > 0){
                    if(need[d] == win[d]){
                        valid --;
                    }
                    win[d] --;
                }
            }
        }
        return res;
    }
}

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

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

示例 1:

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

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0;
        int[] win = new int[256];
        int res = 0;
        while(right < s.length()){
            char c = s.charAt(right);
            right++;
            win[c]++;
            while(win[c] > 1){
                // 收缩以满足条件
                char d = s.charAt(left);
                left++;
                win[d]--;
            }
            // 满足条件更新结果
            res = Math.max(res, right - left);
        }
        return res;
    }
}