题目
题目来源leetcode
leetcode地址：209. 长度最小的子数组，难度：中等。
题目描述(摘自leetcode)：
给定一个含有 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
本地调试代码：
class Solution { public int minSubArrayLen(int target, int[] nums) { ... } public static void main(String[] args) { int[] nums = new int[]{2,3,1,2,4,3}; System.out.println(new Solution().minSubArrayLen(7, nums)); } }
题解
NO1、暴力法（O(n2)）
一开始没啥思路，直接就通过使用暴力方法来进行求解。
思路：遍历一遍数组的过程中，每到一个索引位置就去求长度最小的子数组，每次求到最小子数组时就与原本临时保存的最小数(连续数)进行比较取值。
代码：时间复杂度：O(n2)，实际为n+(n-1)+(n-2)…，不好求到具体的时间复杂度
public int minSubArrayLen(int target, int[] nums) { if (nums.length == 0 || nums == null) { return 0; } int minSize = nums.length + 1; for (int i = 0; i < nums.length; i++) { int num = 0; //从当前索引位置开始往后取到最小值，并得到符合情况的最小长度 for (int j = i; j < nums.length; j++) { num+=nums[j]; if(num>=target){ minSize = Math.min((j - i + 1), minSize); //(j-i+1)<minSize?(j-i+1):minSize => Math.min((j - i + 1), minSize) break; } } } return minSize == nums.length + 1 ? 0 : minSize;//判断一下是否与初始值一致，一致的话说明没有找到符合的最小子数组 }
No2：滑动窗口（O(n)）
思路：详细可见代码随想录—209.长度最小的子数组
需要有两个指针来进行配合，核心是以指针区间中的数值和进行移动。能将No1题解中的大量不必要的情况筛减掉，提升效率。 左指针用一个变量0来作为初始值；右指针使用遍历数组的索引i 首先进行遍历，不断移动右指针到一个满足条件的位置(>=target)，接着开始缩减范围以>=target为条件开始移动左指针，一旦<target就说明缩减的范围已经足够接着需要再去移动右指针往后取寻找其他更小的情况，通过左右指针进行移动筛选比之前暴力法效果好太多！
代码：时间复杂度O(n)。
每次执行for循环中的while实际上并不会执行很多次，一般也就1-3次和原本的for循环次数加起来为O(2n)，可以直接看做是O(n)。 public int minSubArrayLen(int target, int[] nums) { if (nums.length == 0 || nums == null) { return 0; } int minSubLen = nums.length+1;//最大数量 int leftCur = 0; //左指针 int sum = 0;//用于记录当前指针区间中的值 for (int i = 0; i < nums.length; i++) { //i就相当于右指针 sum += nums[i]; while(sum>=target){ //用来移动左指针，减小区间范围，目的是为了之后其他满足sum>=target的情况 int subLen = i - leftCur + 1; //计算当前区间数量 minSubLen = Math.min(subLen, minSubLen);//与之前区间进行比较，得到最小区间数量 sum -= nums[leftCur++];//区间减小值 } } return minSubLen == nums.length + 1 ? 0 : minSubLen; }
