滑动窗口

EmiyaCC 于 2021-07-15 发布

滑动窗口

刷了点题之后发现，滑动窗口的题，基本都是找的是一个区间（或者是这个区间的大小长度），从左到右的遍历数组（也可以是别的数据结构）时，这个区间（也就是滑动窗口）会有所改变。

还有一点就是这个区间时连在一起的，所以类似于 子串 之类的问题，大概率就是用滑动窗口

通用框架

class Solution {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();

    public String slidingWindow(String s, String t) {
        for (int i = 0; i < t.length(); i ++) {
            char c = t.charAt(i);
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int right = -1;
        while (right < s.length()) {
            right += 1;
            // 自定义
            // ...
            while (每次都检测窗口左边界是否可以往右移动) {
                // 自定义
                // ...
                left += 1;
            }
        }
    }
}

和为s的连续正数序列

// https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
class Solution {
    public int[][] findContinuousSequence(int target) {
        int left = 1, right = 1;
        int sum = 1;
        List<int[]> res = new ArrayList<>();
        while (right < target / 2 + 1 && left <= target / 2 + 1) {
            right += 1;
            sum += right;
            while (sum >= target) {
                if (sum == target) {
                    int[] ans = new int[right - left + 1];
                    for (int i = left; i <= right; i ++)
                        ans[i - left] = i;
                    res.add(ans);
                }
                sum -= left;
                left += 1;
            }
        }
        return res.toArray(new int[0][]);
    }
}

最小覆盖子串

// https://leetcode-cn.com/problems/minimum-window-substring/
// 定义最后答案的左边界、右边界以及最短长度。每次都在右边添加一个元素，并同时检测可不可以将滑动窗口左边界往右移动，同时更新滑动窗口的状态
class Solution {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    int ansL = -1;
    int ansR = -1;
    int len = Integer.MAX_VALUE;

    public String minWindow(String s, String t) {
        for (int i = 0; i < t.length(); i ++) {
            char c = t.charAt(i);
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int right = -1;
        while (right < s.length() - 1 && left < s.length()) {
            right += 1;
            if (right < s.length() && need.containsKey(s.charAt(right))) {
                window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);
            }
            while (check() && left <= right) {
                if (right - left + 1 < len) {
                    ansL = left;
                    ansR = right;
                    len = right - left + 1;
                }
                if (need.containsKey(s.charAt(left))) {
                    window.put(s.charAt(left), window.getOrDefault(s.charAt(left), 0) - 1);
                }
                left += 1;
            }
        }
        return ansR == -1 ? "" : s.substring(ansL, ansR + 1);
    }
    boolean check() {
        for (Map.Entry e : need.entrySet()) {
            int val = (int) e.getValue();
            if (window.getOrDefault(e.getKey(), 0) < val) {
                return false;
            }
        }
        return true;
    }
}

// https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-by-chuancey-hkwu/

// 这个是 labuladong 的解法，不需要每次判断是否收缩时都检查一遍map，但是不知道为什么leetcode过不了
class Solution {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    int ansL = -1;
    int ansR = -1;
    int len = Integer.MAX_VALUE;

    public String minWindow(String s, String t) {
        for (int i = 0; i < t.length(); i ++) {
            char c = t.charAt(i);
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int right = 0;
        int vaild = 0;
        while (right < s.length()) {
            char tmpChar1 = s.charAt(right);
            right += 1;
            if (need.containsKey(tmpChar1)) {
                window.put(tmpChar1, window.getOrDefault(tmpChar1, 0) + 1);
                if (need.get(tmpChar1) == window.get(tmpChar1)) {
                    vaild += 1;
                }
            }

            while (vaild == need.size()) {
                if (right - left < len) {
                    ansL = left;
                    ansR = right;
                    len = right - left;
                }
                char tmpChar2 = s.charAt(left);
                left += 1;
                if (need.containsKey(tmpChar2)) {
                    if (need.get(tmpChar2) == window.get(tmpChar2)) {
                        vaild -= 1;
                    }
                    window.put(tmpChar2, window.get(tmpChar2) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(ansL, ansR);
    }
}

字符串的排列

// https://leetcode-cn.com/problems/permutation-in-string/
// 改自上题的第一解
class Solution {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();

    public boolean checkInclusion(String s1, String s2) {
        for (int i = 0; i < s1.length(); i ++) {
            char c = s1.charAt(i);
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0;
        int right = -1;
        while (right < s2.length() - 1 && left < s2.length()) {
            right += 1;
            if (right < s2.length() && need.containsKey(s2.charAt(right))) {
                window.put(s2.charAt(right), window.getOrDefault(s2.charAt(right), 0) + 1);
            }
            // 在是否收缩的情况判断
            while (right - left + 1 >= s1.length()) {
                // 先判断总体长度是否符合，在判断字符是否都对的上
                if (check()) {
                    return true;
                }
                if (need.containsKey(s2.charAt(left))) {
                    window.put(s2.charAt(left), window.getOrDefault(s2.charAt(left), 0) - 1);
                }
                left += 1;
            }
        }
        return false;
    }
    boolean check() {
        for (Map.Entry e : need.entrySet()) {
            int val = (int) e.getValue();
            if (window.getOrDefault(e.getKey(), 0) != val) {
                return false;
            }
        }
        return true;
    }
}

// 跟上题一样，C 改成 Java，就跑不通了，以后研究
class Solution {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();

    public boolean checkInclusion(String s1, String s2) {
        for (int i = 0; i < s1.length(); i ++) {
            need.put(s1.charAt(i), need.getOrDefault(s1.charAt(i), 0) + 1);
        }
        int left = 0;
        int right = 0;
        int vaild = 0;
        while (right < s2.length()) {
            char tmpChar1 = s2.charAt(right);
            right += 1;
            if (need.containsKey(tmpChar1)) {
                window.put(tmpChar1, window.getOrDefault(tmpChar1, 0) + 1);
                if (need.get(tmpChar1) == window.get(tmpChar1)) {
                    vaild += 1;
                }
            }

            while (right - left >= s1.length()) {
                if (vaild == need.size()) {
                    return true;
                }
                char tmpChar2 = s2.charAt(left);
                left += 1;
                if (need.containsKey(tmpChar2)) {
                    if (need.get(tmpChar2) == window.get(tmpChar2)) {
                        vaild -= 1;
                    }
                    window.put(tmpChar2, window.get(tmpChar2) - 1);
                }
            }
        }
        return false;
    }
}

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

// https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
// 基本上跟上题一样，多个记录 left 的步骤
class Solution {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();

    public List<Integer> findAnagrams(String s, String p) {
        for (int i = 0; i < p.length(); i ++) {
            need.put(p.charAt(i), need.getOrDefault(p.charAt(i), 0) + 1);
        }

        List<Integer> lis = new ArrayList<>();
        int left = 0;
        int right = -1;
        while (right < s.length() - 1 && left < s.length()) {
            right += 1;
            if (right < s.length() && need.containsKey(s.charAt(right))) {
                window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);
            }

            while (right - left + 1 >= p.length()) {
                if (check()) {
                    lis.add(left);
                }
                if (need.containsKey(s.charAt(left))) {
                    window.put(s.charAt(left), window.get(s.charAt(left)) - 1);
                }
                left += 1;
            }
        }
        return lis;
    }

    boolean check() {
        for (Map.Entry e : need.entrySet()) {
            int val = (int) e.getValue();
            if (window.getOrDefault(e.getKey(), 0) != val) {
                return false;
            }
        }
        return true;
    }
}

无重复字符的最长子串

// https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
class Solution {
    Map<Character, Integer> window = new HashMap<>();
    int len = 0;

    public int lengthOfLongestSubstring(String s) {
        int left = 0;
        int right = -1;
        while (left < s.length() && right < s.length() - 1) {
            right += 1;
            window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);
            // check是用来判断是否需要收缩
            while (checkIn()) {
                window.put(s.charAt(left), window.get(s.charAt(left)) - 1);
                left += 1;
            }
            // 更新边界
            if (right - left + 1 > len) {
                len = right - left + 1;
            }
        }
        return len;
    }

    boolean checkIn() {
        for (Map.Entry e : window.entrySet()) {
            int val = (int) e.getValue();
            if (val > 1) {
                return true;
            }
        }
        return false;
    }
}

// 简便版本，
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int i = -1;
        int res = 0;
        for (int j = 0; j < s.length() ; j ++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(i,map.get(s.charAt(j)));
            }
            map.put(s.charAt(j), j);
            res = Math.max(res, j - i);
        }
        return res;
    }
}

滑动窗口的扩展

去除重复字母

// https://leetcode-cn.com/problems/remove-duplicate-letters/
// 解题思路：首先用 count 记录字符串每个字符的个数和，再用 StringBuilder 作为滑动窗口载体，并用 vis 记录在窗口中的是否出现对应字符，每次 StringBuilder 加入一个字符 ch 之前，首先判断窗口是否右该字符，没有则加入，然后循环判断 StringBuilder 尾部的字符是否满足：1. 大于 ch；2. 字符串后面是否还有该尾部字符，如果满足这两条条件，则删除该尾部字符，反复上述操作直到获得结果
class Solution {
    public String removeDuplicateLetters(String s) {
        boolean[] vis = new boolean[26];
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i ++) {
            count[s.charAt(i) - 'a'] += 1;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i ++) {
            char ch = s.charAt(i);
            if (!vis[ch - 'a']) {
                while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch) {
                    if (count[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                        vis[sb.charAt(sb.length() - 1) - 'a'] = false;
                        sb.deleteCharAt(sb.length() - 1);
                    }
                    // 注意这个 else，表示若尾部元素在字符串后面没有了，则需要保存这个元素及其前面的元素，由于前面的元素肯定有比尾部元素小，为了保证最小的字符序，那么前面的就不可以删除了，所有才有了此处的 b
                    else {
                        break;
                    }
                }
                vis[ch - 'a'] = true;
                sb.append(ch);
            }
            count[ch - 'a'] -= 1;
        }
        return sb.toString();
    }
}

替换后的最长重复字符

// https://leetcode-cn.com/problems/longest-repeating-character-replacement/
class Solution {
    public int characterReplacement(String s, int k) {
        int left = 0, right = -1;
        int len = s.length();
        int[] records = new int[26];
        int max = 0;
        while (right < len - 1 && left < len) {
            right += 1;
            records[s.charAt(right) - 'A'] += 1;
            max = Math.max(max, records[s.charAt(right) - 'A']);
            // 注意这里用的是 if，用 if 虽然最后的区间里面的数不满足条件，但是这个区间大小是最大的区间大小，这里的逻辑是不让区间变小
            if (right - left + 1 - max > k) {
                records[s.charAt(left) - 'A'] -= 1;
                left += 1;
            }
        }
        return right - left + 1;
    }
}

// 正常的版本，每次都收缩到满足条件
class Solution {
    public int characterReplacement(String s, int k) {
        int left = 0, right = -1;
        int len = s.length();
        int[] records = new int[26];
        int max = 0;
        int res = 0;
        while (right < len - 1 && left < len) {
            right += 1;
            records[s.charAt(right) - 'A'] += 1;
            max = Math.max(max, records[s.charAt(right) - 'A']);
            while (right - left + 1 - max > k) {
                records[s.charAt(left) - 'A'] -= 1;
                left += 1;
            }
            if (right - left + 1 > res) res = right - left + 1;
        }
        return res;
    }
}

最大连续1的个数 III

// https://leetcode-cn.com/problems/max-consecutive-ones-iii/
class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0;
        int right = -1;
        int len = nums.length;
        int record = 0;
        while (right < len - 1 && left < len) {
            right += 1;
            if (nums[right] == 1) record += 1;
            // 用的是 if
            if (right - left + 1 - record > k) {
                if (nums[left] == 1) record -= 1;
                left += 1;
            }
        }
        return right - left + 1;
    }
}