滑动窗口问题是一种重要的算法思路，主要用来解决数组/字符串的子元素问题，可以将嵌套的循环问题优化成单层循环。下面收集了几道滑动窗口相关的算法题，我们一起学习下。

长度最短的子数组

题目地址

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

示例:

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

暴力解法

这道题最开始容易想到使用暴力法直接找到所有的子数组进行比较，代码也比较容易写出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Integer count = null;
        for (int i = 0; i < nums.length - 1; i++) {
            int sum = nums[i];
            int c = 1;
            for (int j = i + 1; j < nums.length && sum < s; j++) {
                if (sum < s) {
                    sum += nums[j];
                    c++;
                }
            }
            if (sum >= s) {
                count = count == null ? c : Math.min(c, count);
            }
        }
        return count == null ? 0 : count;
 
    }
}

逻辑还算简单，就是找出来所有大于等于sum的子数组。
时间复杂度：O(n^2)
空间复杂度：O(1)

差分+二分查找解法

下面我们尝试优化下这个解法，我们使用记录一个前缀和数组，利用差分的特性，可以快速的找到大于等于sum的位置。这个查找过程我们使用二分查找，每次查找的时间复杂度为O(logn)，需要查找n次找出最小值，所以总的时间复杂度为O(nlog(n))，比暴力的O(n^2)有所优化。

顺便回顾下差分和前缀和：
前缀和: 给定一个数组A[1..n]，前缀和数组PrefixSum[1..n]定义为：PrefixSum[i] = A[0]+A[1]+…+A[i-1]；

差分：前缀和数组中任意两项的差，同时等于这两个索引中所有元素的和。如本题中用来计算这两个索引之间的所有元素和是否大于等于sum。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] sums = new int[nums.length + 1];
        // 声明一个n+1长度的数组，然后计算前缀和
        for (int i = 1; i < sums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < sums.length; i++) {
            // 用二分查找，找到大于sum的右索引
            int right = bs(sums, i + 1, sums[i] + s);
            if (right == sums.length) {
                break;
            }
            ans = Math.min(ans, right - i);
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
 
    }
 
    private int bs(int[] sums, int left, int key) {
        int l = left, r = sums.length - 1;
        while (l <= r) {
            int m = (l + r) >>> 1;
            if (key <= sums[m]) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

时间复杂度：O(nlog(n))
空间复杂度: O(n)

滑动窗口解法

接下来我们看下还有没有办法优化，我们发现数组中的元素没有负数（关键，若有负数，则不能使用滑动窗口），我们创建一个left变量用来标记右边界，然后不断向右扩展，直到找到当前和sum大于等于s时，向右移动左边界,并尝试记录最小值，最小值一定会在滑动窗口中产生。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // 使用left记录左边索引，逐步向右收缩
        int left = 0;
        int sum = 0;
        int ans = Integer.MAX_VALUE;
        for (int i = 0 ; i < nums.length; i++) {
            sum += nums[i];
            // 尝试收缩右边界
            while (sum >= s) {
                ans = Math.min(ans, i - left + 1);
                sum -= nums[left++];
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

时间复杂度 O(n)
空间复杂度 O(1)

发表评论

邮箱地址不会被公开。 必填项已用*标注