#|LeetCode 209. 长度最小的子数组（中等、数组）day23 leetcode|算法|java|数组

【#|LeetCode 209. 长度最小的子数组（中等、数组）day23】题目描述：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+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

提示：

1 <= target <= 109 1 <= nums.length <= 105 1 <= nums[i] <= 105

方法1：暴力破解

使用两个for循环，外层for循环固定一个开始的数组元素nums[i]，内层for循环从nums[i]开始进行累加，直到sum >= target结束内层for循环，然后判断更新最小数组长度即可

。
方法2：滑动窗口

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。在本题中实现滑动窗口，主要确定如下三点：窗口内是什么？如何移动窗口的起始位置？如何移动窗口的结束位置？窗口就是满足其和 ≥ target 的长度最小的连续子数组。窗口的起始位置如何移动：如果当前窗口的值大于target了，窗口就要向前移动了（sum该缩小了）。窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。参考连接：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html#%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3

文章图片

代码实现：

public class MinSubArrayLenDemo { public static void main(String[] args) { int target = 11; int[] nums = {1,1,1,1,1,1,1,1}; System.out.println(minSubArrayLen(target, nums)); }/** * 暴力破解法，时间复杂度为O(n^2) * @param target * @param nums * @return */ public static int minSubArrayLen(int target, int[] nums){ int result = Integer.MAX_VALUE; // 假设连续最大数组长度为lengthfor (int i = 0; i < nums.length; i++) { int sum = 0; for (int j = i; j < nums.length; j++) { sum += nums[j]; // 累加 if(sum < target){// 如果当前累加和小于target则继续进行循环 continue; }else { result = Math.min(result, j - i + 1); break; } } } // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列 return result == Integer.MAX_VALUE ? 0 : result; }/** * 滑动窗口 * @param target * @param nums * @return */ public static int minSubArrayLen1(int target, int[] nums){ int left = 0; // 滑动窗口的起始位置 int sum = 0; // 滑动窗口的数值之和 int result = Integer.MAX_VALUE; for (int right = 0; right < nums.length; right++) {// right为滑动窗口的结束位置 sum += nums[right]; // 注意这里使用while，每次更新 left（起始位置），并不断比较子序列是否符合条件 while (sum >= target){ result = Math.min(result, right - left + 1); // 获取最短子序列长度 sum -= nums[left++]; // 这里体现出滑动窗口的精髓之处 } } // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列 return result == Integer.MAX_VALUE ? 0 : result; } }

收获：

第一次使用滑动窗口的知识解题，使用滑动窗口主要有三个点主要注意： 第一就是滑动窗口里面的内容有什么意义，比如说本题滑动窗口里面数据元素的和代表子序列的和，然后与target进行比较； 第二就是滑动窗口的起始位置在什么情况下继续向前移动，本题在sum >= target时起始位置left向右移动(向前)，以缩小滑动窗口的长度，找到最小的滑动窗口； 第三就是滑动窗口的结束位置在什么情况下继续向前移动，这一个就很好理解了，当滑动窗口内元素的和sum < target的时候 ，滑动窗口结束位置需要继续向前移动，不断增大滑动窗口内元素和sum, 直到sum >= target

.
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-size-subarray-sum