题目地址(209. 长度最小的子数组)

https://leetcode-cn.com/problems/minimum-size-subarray-sum/

题目描述

  1. 给定一个含有 n 个正整数的数组和一个正整数 target 。
  3. 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
  7. 示例 1：
  9. 输入：target = 7, nums = [2,3,1,2,4,3]
  10. 输出：2
  11. 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
  14. 示例 2：
  16. 输入：target = 4, nums = [1,4,4]
  17. 输出：1
  20. 示例 3：
  22. 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
  23. 输出：0
  28. 提示：
  30. 1 <= target <= 109
  31. 1 <= nums.length <= 105
  32. 1 <= nums[i] <= 105
  36. 进阶：
  38. 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

前置知识


公司

  • 暂无

思路

209.长度最小的子数组.gif
其实从动画中可以发现滑动窗口也可以理解为双指针法的一种！只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。

在本题中实现滑动窗口，主要确定如下三点：

  1. 窗口内是什么？
  2. 如何移动窗口的起始位置？
  3. 如何移动窗口的结束位置？

窗口内就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。

可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。

为什么时间复杂度是O(n)。

不要以为for里放一个while就以为是$O(n^2)$啊， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被被操作两次，所以时间复杂度是2 * n 也就是$O(n)$。

关键点

  • 滑动窗口

就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

代码

  • 语言支持：Java

Java Code:

  • 暴力解法 ```java

class Solution { public int minSubArrayLen(int target, int[] nums) {

  1.     int sum = 0, length = 0, result = Integer.MAX_VALUE;
  2.     for (int i = 0; i < nums.length; i++) {
  3.         sum = 0;
  4.         for (int j = i; j < nums.length; j++) {
  5.             sum += nums[j];
  6.             if (sum >= target) {
  7.                 length = j - i + 1;
  8.                 result = length < result ? length : result;
  9.                 break;
  10.             }
  11.         }
  12.     }
  13.     return result == Integer.MAX_VALUE ? 0 : result;
  14. }

}

  2. - 滑动窗口
  3. ```java
  4. class Solution {
  5.     public int minSubArrayLen(int target,
  6.                               int[] nums) {
  7.         //最终返回结果
  8.         int result = Integer.MAX_VALUE;
  9.         //慢指针
  10.         int slow = 0;
  11.         //滑动窗口中的值总和
  12.         int sum = 0;
  13.         //滑动窗口的长度
  14.         int size = 0;
  15.         for (int fast = 0; fast < nums.length; fast++) {
  16.             //每次循环 将快指针指到的值加起来
  17.             sum += nums[fast];
  18.             //当总和大于给定的值时
  19.             while (sum >= target) {
  20.                 //取子列长度
  21.                 size = fast - slow + 1;
  22.                 //判断数组长度是否小于最终返回的值
  23.                 result = size < result ? size : result;
  24.                 //数组总和减去当前的慢指针指向的值 并继续判断 如果还是小于 就继续让慢指针++ 如果大于的话 就让快指针继续往前走
  25.                 sum -= nums[slow++];
  26.             }
  27.         }
  28.         //返回最终结果 如果等于原来的数组最大值时 就返回0 因为数组中没有合适的结果
  29.         return result == Integer.MAX_VALUE ? 0 : result;
  30.     }
  31. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：暴力解法 209. 长度最小的子数组 - 图2#card=math&code=O%28n%5E2%29&id=SOi2z) 滑动窗口 209. 长度最小的子数组 - 图3#card=math&code=O%28n%29&id=UAdKl)
  • 空间复杂度：209. 长度最小的子数组 - 图4#card=math&code=O%28n%29&id=qLk92)