滑动窗口算法
滑动窗口问题是一种重要的算法思路,主要用来解决数组/字符串的子元素问题,可以将嵌套的循环问题优化成单层循环。下面收集了几道滑动窗口相关的算法题,我们一起学习下。
长度最短的子数组
给定一个含有 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)