每日算法题 10

题目209.长度最小的子数组要求给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的子数组[numsl, numsl1, ..., 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 low0; int high0; int sum0; int minInteger.MAX_VALUE; while(highnums.length){ sumnums[high]; high; while(sumtarget){ minMath.min(min,high-low); sum-nums[low]; low; } } return minInteger.MAX_VALUE?0:min; } }小舟有话说在这里提到了滑动窗口该算法本质上是双指针的一种具体应用场景用来解决子数组/子串/子序列等问题具体用法用两个指针划定一个窗口通过移动右指针扩大窗口移动左指针收缩窗口在窗口内维护满足条件的子数组如果能帮助到你点点关注下次不迷路~