【面试算法笔记】0104-数组-滑动窗口

面试算法笔记2026年4月·算法LeetCode
zbhgis 浩瀚地学896 字5 分钟
创建于 更新于

个人主页：https://github.com/zbhgis

前言

本系列主要记录自己学习算法的过程中的感悟。

力扣209. 长度最小的子数组

链接：https://leetcode.cn/problems/minimum-size-subarray-sum/description/

注意点

滑动窗口做法。

这类题的注意点在于窗口长度的控制。

1.定义两个指针，右指针先移动，移动到某个位置后，满足题目所需的target条件之后，也就是sum >= target之后，开始尝试移动左指针，缩小窗口。

2.在第一步操作的过程中，需要一个额外的sum变量，来实时计算窗口的总和，right前进，就加上新的数，left前进，就减去这个数。

代码

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

时空复杂度分析

虽然是双重循环，但是由于内层和外层循环，加起来总共访问2n最多，所以最坏情况O(2n)=O(n)

空间复杂度O(1)

力扣904. 水果成篮

链接：https://leetcode.cn/problems/fruit-into-baskets/description/

注意点

滑动窗口做法。

1.类似于上一题，这题需要额外创建一个数组来记录水果的类型。

2.定义两个指针，右指针先移动，移动在某个某个位置后，满足题目所需的水果类型只有两个之后，进一步移动尝试移动右指针直到水果类型有三个（就是type > 2或者type == 3的时候），然后再移动左指针来收缩（因为没办法精确地停下来），缩小窗口。

3.其他都类似，就是写起来麻烦一些，此时通过cnt数组来记录水果类型的个数，作用类似于上一题的sum。

4.还有就是记录类型种类type的时候，开始记录种类的时候，需要先cnt++，再type++，移除记录种类的时候，则是先type++，再cnt++；

代码

Java
class Solution {
    public int totalFruit(int[] fruits) {
        int left = 0;
        int len = 0;
        int type = 0;
        int[] cnt = new int[fruits.length];
        for (int right = 0; right < fruits.length; right ++) {
            int in = fruits[right];
            if (cnt[in] == 0) type ++;
            cnt[in] ++;
            
            while (type > 2) {
                int out = fruits[left];
                cnt[out] --;
                if (cnt[out] == 0) type --;
                left ++;
            }
            len = Math.max(len, right - left + 1);
        }
        return len;
    }
}

时空复杂度分析

虽然是双重循环，但是由于内层和外层循环，加起来总共访问2n最多，所以最坏情况O(2n)=O(n)

空间复杂度O(n)，n为fruits的长度

力扣76. 最小覆盖子串

链接：https://leetcode.cn/problems/minimum-window-substring/description/

注意点

滑动窗口做法。

1.类似于上一题，不过这题更难，使用普遍的滑动窗口也能成功，下面是优化版本。

2.首先定义一个diff，表示窗口每种字母个数 - t每种字母个数。第一步先获取到窗口为空的情况下，两者的差异。之后类似于前两题，开始定义两个指针。这题需要额外定义ansLeft 和ansRight，因为这个题返回的是具体的数组，不是长度了，所以要考虑到最后窗口为空的情况。额外定义一个geCnt，表示窗口内有geCnt种字母的出现次数 >= t中相应字母的出现次数。

3.开始遍历，右指针先移动，对应的diff也随之更新。当diff[s[right]] == 0的时候，说明出现了新字符，geCnt也随之更新。直到geCnt == kinds，说明现在符合题目所要求的字符个数了，开始移动左指针。开始更新窗口长度，用ansLeft 和 ansRight记录，方便后续在循环外返回结果。

代码

SQL
class Solution {
    public String minWindow(String S, String t) {
        int[] diff = new int[128];
        int kinds = 0;
        for (char c : t.toCharArray()) {
            if (diff[c] == 0) {
                kinds ++;
            }
            diff[c] --;
        }

        int left = 0;
        char[] s = S.toCharArray();
        int m = s.length;
        int ansLeft = -1;
        int ansRight = m;
        int geCnt = 0;
        for (int right = 0; right < m; right ++) {
            char c = s[right];
            diff[c] ++;
            if (diff[c] == 0) {
                geCnt ++;
            }
            
            while (geCnt == kinds) {
                if (right - left < ansRight - ansLeft) {
                    ansLeft = left;
                    ansRight = right;
                }

                char x = s[left];
                if (diff[x] == 0) {
                    geCnt --;
                }
                diff[x] --;
                left ++;
            }
        }
        return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);
    }
}

时空复杂度分析

虽然是双重循环，但是由于内层和外层循环，加起来总共访问2n最多，所以最坏情况O(2n)=O(n)

空间复杂度O(128)，即O(1)

参考

https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html