滑动窗口专项练习

前言

本篇文章以「滑动窗口」为专题，罗列了高频重要的相关题目，而且本文所有题目的代码思路严格保持一致，也就是遵循通用的算法模版，详情可见滑动窗口～

题目


xxxxxxxxxx
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int n = s.length(), ans = 0;
    int l = 0, r = 0;
    while (r < n) {
        // 窗口扩张
        char c = s.charAt(r++);
        window.put(c, window.getOrDefault(c, 0) + 1);

        // 窗口收缩，一直保持窗口内无重复字符
        while (window.get(c) > 1) {
            char d = s.charAt(l++);
            window.put(d, window.get(d) - 1);
        }

        // 窗口内一定无重复字符，更新答案
        ans = Math.max(ans, r - l);
    }
    return ans;
}

题目详情可见 209. 长度最小的子数组


xxxxxxxxxx
public int minSubArrayLen(int target, int[] nums) {
    int window = 0;
    int n = nums.length, ans = n + 1;
    int l = 0, r = 0;
    while (r < n) {
        // 窗口扩张
        int c = nums[r++];
        window += c;

        // 窗口收缩
        while (window >= target) {
            // 窗口内的元素和一定大于 target，更新答案
            ans = Math.min(ans, r - l);

            int d = nums[l++];
            window -= d;
        }
    }
    return ans == n + 1 ? 0 : ans;
}

题目详情可见 2461. 长度为 K 子数组中的最大和


xxxxxxxxxx
public long maximumSubarraySum(int[] nums, int k) {
    Map<Integer, Integer> window = new HashMap<>();
    int n = nums.length;
    long sum = 0, ans = 0;
    int l = 0, r = 0;
    while (r < n) {
        // 窗口扩张
        int c = nums[r++];
        sum += c;
        window.put(c, window.getOrDefault(c, 0) + 1);

        // 窗口收缩，一直保持窗口内无重复元素 且 窗口长度 <= k
        while (window.get(c) > 1 || r - l > k) {
            int d = nums[l++];
            sum -= d;
            window.put(d, window.get(d) - 1);
        }

        // 窗口内一定无重复元素，但需要保证窗口大小为 k，更新答案
        if (r - l == k) ans = Math.max(ans, sum);
    }
    return ans;
}

题目详情可见 904. 水果成篮


xxxxxxxxxx
public int totalFruit(int[] fruits) {
    Map<Integer, Integer> window = new HashMap<>();
    int n = fruits.length, ans = 0;
    int l = 0, r = 0;
    while (r < n) {
        // 窗口扩张
        int c = fruits[r++];
        window.put(c, window.getOrDefault(c, 0) + 1);

        // 窗口收缩，一直保持窗口内不同元素的个数为 2
        while (window.size() > 2) {
            int d = fruits[l++];
            window.put(d, window.get(d) - 1);
            if (window.get(d) == 0) window.remove(d);  // 删除数量为 0 的元素
        }

        // 窗口内不同元素的个数一定小于等于 2，更新答案
        ans = Math.max(ans, r - l);
    }
    return ans;
}

题目详情可见 438. 找到字符串中所有字母异位词


xxxxxxxxxx
public List<Integer> findAnagrams(String s, String p) {
    Map<Character, Integer> window = new HashMap<>();
    Map<Character, Integer> need = new HashMap<>();
    for (char c : p.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);
    List<Integer> ans = new ArrayList<>();
    int n = s.length(), valid  = 0;
    int l = 0, r = 0;
    while (r < n) {
        // 窗口扩张
        char c = s.charAt(r++);
        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()) {
            // 窗口内包含 p 的所有字符，如果长度也相等就一定是异位词子串，更新答案
            if (r - l == p.length()) ans.add(l);

            char d = s.charAt(l++);
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) valid--;
                window.put(d, window.get(d) - 1);
            }
        }
    }
    return ans;
}

题目详情可见 76. 最小覆盖子串


xxxxxxxxxx
public String minWindow(String s, String t) {
    Map<Character, Integer> window = new HashMap<>();
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);
    int n = s.length(), valid = 0, mn = n + 1, idx = 0;
    int l = 0, r = 0;
    while (r < n) {
        // 窗口扩张
        char c = s.charAt(r++);
        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()) {
            // 窗口内包含 t 的所有字符，更新答案
            if (r - l < mn) {
                mn = r - l;
                idx = l;
            }
            char d = s.charAt(l++);
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) valid--;
                window.put(d, window.get(d) - 1);
            }
        }
    }
    return mn == n + 1 ? "" : s.substring(idx, idx + mn);
}

题目详情可见 1658. 将 x 减到 0 的最小操作数


xxxxxxxxxx
public int minOperations(int[] nums, int x) {
    int window = 0;
    int sum = Arrays.stream(nums).sum();
    int n = nums.length, ans = n + 1;
    int l = 0, r = 0;
    while (r < n) {
        // 窗口扩张
        int c = nums[r++];
        window += c;

        // 窗口收缩
        while (l < n && sum - window < x) {
            int d = nums[l++];
            window -= d;
        }
        
        // 窗口之外的元素和为 x，更新答案
        if (sum - window == x) ans = Math.min(ans, n - r + l);
    }
    return ans == n + 1 ? -1 : ans;
}

题目详情可见 2516. 每种字符至少取 K 个


xxxxxxxxxx
public int takeCharacters(String s, int k) {
    int[] cnt = new int[3];
    for (char c : s.toCharArray()) cnt[c - 'a']++;
    for (int x : cnt) {
        if (x < k) return -1;
    }
    int n = s.length(), ans = 0;
    int l = 0, r = 0;
    while (r < n) {
        // 窗口扩张
        char c = s.charAt(r++);
        cnt[c - 'a']--;

        // 窗口收缩
        while (cnt[0] < k || cnt[1] < k || cnt[2] < k) {
            char d = s.charAt(l++);
            cnt[d - 'a']++;
        }

        // 窗口之外的元素中一定分别有 k 个 a、b、c，更新答案
        ans = Math.max(ans, r - l);
    }
    return n - ans;
}