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

长度最短的子数组

题目地址

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

示例:

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

暴力解法

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

逻辑还算简单,就是找出来所有大于等于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。

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

滑动窗口解法

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

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

发表评论

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