每日一题 | 长度最小的子数组

长度最小的子数组（209. 中等难度）

题目来源

LeetCode 209. 长度最小的子数组[1]

题目描述

给定一个含有n个正整数的数组和一个正整数target。

找出该数组中满足其总和大于等于target的长度最小的子数组[numsi, numsi+1, ..., numsr-1, numsr]，返回其长度。如果不存在符合条件的子数组，返回 0 。

示例

示例 1：

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

示例 2：

输入：target = 4, nums = [1,4,4]输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]输出：0

作者思考

暴力法：直接遍历所有长度的子数组并求和，如果和大于等于target就把这次长度与上次的进行比较，更新最小长度。时间复杂度O(n2)

前缀和+二分查找：所谓前缀和就是所给数组的前n个元素的和。使用sums[i](这里i从1开始)表示nums[0]到nums[i-1]的和，这样我们可以用sum[j]-sums[i-1]得到子数组nums[i-1...j-1]的和。

这里使用方块面积来表示元素的和，sums[]和nums[]的对应关系如下：

思想分析：

将元素和抽象出来，每一个面积块代表对应元素和。每一个面积块不断减去前面的面积块，就可以得到任意区间的面积块(即任意区间的元素和)

对于每一个区间的元素和，找到最小的j，使得sums[j] - sums[i-1] >= s

即 sums[j] >= s + sums[i-1]，由于sums数组单调递增，找最小的j就是找最小满足这个不等式的sums[j]

使用Arrays.binarySearch()二分查找，可以找到sums[j]应该在sums数组中的位置，从而确定j。由于sums和nums的元素位置是对应的，继而可以确定区间。

按照代码的流程分析：

滑动窗口法：也属于双指针的一种，所谓滑动窗口就是利用双指针不断变化求和区间。

如果说暴力解法是求出所有区间，然后从所有区间中找到符合条件的，时间复杂度为O(n2)；前缀和利用额外的空间使得求出所有区间，时间复杂度变为O(n)，二分查找使得找到符合条件的，时间复杂变为O(logn)；以上两种方法都是固定某一端指针，求出所有区间再找出符合条件的。

而滑动窗口法则是将两端指针都不固定，直接找出符合条件的区间。左端为0时，右端走到符合条件时，从0到右端再往右的所有区间就都不需要判断了；此时"固定"右端，左端再往右走到最后一次符合条件时，右端到左端再往左的所有区间就都不需要判断了。此时再"固定"左端，移动右端，如此往复。(官方题解中有动画展示，此处不再重复)

另一种理解方式为"右进左出"的双端队列。依次将元素从右端入队，当队内元素和满足>=S的条件时，记录队内元素长度，左端的元素再依次出队，直到队内元素不再满足，右端继续入队，重复这个过程。

🧠 题解

// 暴力法在这里就不再展示// 前缀和+ 二分查找class Solution {   public int minSubArrayLen(int s, int[] nums) {       int n = nums.length;       if (n == 0) return 0;       int ans = Integer.MAX_VALUE;       int[] sums = new int[n + 1];       // 前缀和数组，sums[i] 表示前 i 个元素的和       // 例如：       // sums[0] = 0       // sums[1] = nums[0]       // sums[2] = nums[0] + nums[1]

      for (int i = 1; i <= n; i++) {           sums[i] = sums[i - 1] + nums[i - 1];       }       for (int i = 1; i <= n; i++) {           int target = s + sums[i - 1]; // 我们要找 sums[j] >= target           int bound = Arrays.binarySearch(sums, target);           // 这里为什么能确定sums[j]就是满足不等式的最小值?           //了解一下Arrays.binarySearch方法的返回值，尤其是没有找到目标值时           // 注意sums是递增的           if (bound < 0) {               // 如果没找到，binarySearch 返回插入点（负数）               bound = -bound - 1;           }

          if (bound <= n) {               ans = Math.min(ans, bound - (i - 1)); // 更新最短子数组长度           }       }       return ans == Integer.MAX_VALUE ? 0 : ans;   }}

// 滑动窗口// 作者：力扣官方题解// 链接：https://leetcode.cn/problems/minimum-size-subarray-sum/solutions/305704/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/class Solution {   public int minSubArrayLen(int s, int[] nums) {       int n = nums.length;       if (n == 0) {           return 0;       }       int ans = Integer.MAX_VALUE;       int start = 0, end = 0;       int sum = 0;       while (end < n) {           sum += nums[end];           while (sum >= s) {               ans = Math.min(ans, end - start + 1);               sum -= nums[start];               start++;           }           end++;       }       return ans == Integer.MAX_VALUE ? 0 : ans;   }}

References

[1]LeetCode 209. 长度最小的子数组: https://leetcode.cn/problems/minimum-size-subarray-sum/description/