博客

分享几道和「滑动窗口」有关的算法面试题

  • Post category:Python

下面我来详细讲解一下分享几道和「滑动窗口」有关的算法面试题的完整攻略。

什么是滑动窗口？

滑动窗口算法，是数组/字符串问题中的常见思路。它可以用来解决一些查找或计数问题。例如，给定一个数组，找出其中连续的子数组，满足某些条件，需要注意的是，这个子数组的大小是可以变化的（即滑动窗口），你需要求出这个子数组的最大或者最小值。

使用滑动窗口的具体技巧

  1. 窗口的大小变化要具有单调性：窗口的大小是变化的，但是我们可以要求它的变化应该具有单调性。例如，在做求最大值/最小值的时候，窗口一般要求是递增/递减的。
  2. 双指针技巧：滑动窗口问题中，左右指针分别从数列的两端开始，每次只挪动其中一个，以满足窗口的单调性要求。
  3. 如何修改窗口内容：窗口是可以动态修改的，具体修改策略根据题目而定。

滑动窗口类型的面试题

接下来我们来看两道滑动窗口类型的面试题：

题目一：最小覆盖子串

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字符的最小子串。

示例 1:

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

解题思路

这道题是滑动窗口中比较经典的一道题，我们可以用滑动窗口算法进行解决。

  1. 我们用 HashMap 存储 needs 中的字符和它们的数量
  2. 窗口左右指针 l 和 r 初始化为 0
  3. while 循环的条件是右指针移动到字符串 S 的末尾
  4. 如果当前右指针指向的字符是 needs 中的字符，则该字符对应的值减 1。直到该字符在需要的数量中为 0
    • 如果当前滑动窗口已经包含了 T 中的所有字符，判断当前区间是否为所有区间中最小的，则更新最小区间。并弹出左指针指向的字符，同时窗口左指针加 1，并设置窗口是否包含 T 中所有字符的状态为未包含。
  5. 否则，右指针继续向右移

代码如下：

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> needs = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            needs.put(c, needs.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        int valid = 0;
        // 记录最小覆盖子串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            // c 是将移入窗口的字符
            char c = s.charAt(right);
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新
            if (needs.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c).equals(needs.get(c))) {
                    valid++;
                }
            }
            // 判断左侧窗口是否要收缩
            while (valid == needs.size()) {
                // 更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (needs.containsKey(d)) {
                    if (window.get(d).equals(needs.get(d))) {
                        valid--;
                    }
                    window.put(d, window.getOrDefault(d, 0) - 1);
                }

            }
        }
        // 返回最小覆盖子串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

题目二：长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例 1:

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下最小的子数组。

解题思路

这道题目与上面的题目十分类似，也可以采用滑动窗口的算法进行解答。具体解题思路如下：

  1. 我们用双指针在数组上滑动
  2. 用 sum 来记录当前窗口中元素之和
  3. 当 sum 大于等于 s 时，更新 minLen，并将左指针向右移动，更新窗口的和
  4. 当 sum 小于 s 时，将右指针向右移动，扩大窗口，更新 sum

代码如下：

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int left = 0, right = 0;
        int sum = 0, minLen = Integer.MAX_VALUE;
        while (right < n) {
            sum += nums[right];
            while (sum >= s) {
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left++];
            }
            right++;
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}

以上就是滑动窗口算法的攻略，希望能给大家带来一些帮助。

Tags: ,