每日算法题 10

题目

209.长度最小的子数组

要求

给定一个含有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

思路

又是我们的老朋友，通过双指针来指定窗口大小：初始左右指针都指向第一个元素，把右指针的所指向元素加入窗口并向右移一位，扩大右边界，如果当前窗口的和>=s，尝试收缩左边界（左指针向右移一位），找更小的窗口，就这样不断循环（>=s收缩左边界，<s扩大右边界）同时记录最小窗口长度

代码

class Solution { public int minSubArrayLen(int target, int[] nums) { int low=0; int high=0; int sum=0; int min=Integer.MAX_VALUE; while(high<nums.length){ sum+=nums[high]; high++; while(sum>=target){ min=Math.min(min,high-low); sum-=nums[low]; low++; } } return min==Integer.MAX_VALUE?0:min; } }

小舟有话说

在这里提到了滑动窗口，该算法本质上是双指针的一种具体应用场景，用来解决子数组/子串/子序列等问题

具体用法：用两个指针划定一个窗口，通过移动右指针扩大窗口，移动左指针收缩窗口，在窗口内维护满足条件的子数组

如果能帮助到你，点点关注，下次不迷路~