leetcode第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
暴力解法:双层for循环遍历
滑动窗口:依次扩大右侧窗口直到滑动窗口内的子数组符合条件,再逐步缩小左侧窗口直到窗口内的数组不符合条件;反复操作,直到右侧窗口到达数组边界
class Solution { public int minSubArrayLen(int target, int[] nums) { // 左闭右开 int start = 0, end = 0; int sum = 0; int res = Integer.MAX_VALUE; while (end < nums.length) { // 扩大右侧窗口直到滑动窗口内的子数组符合条件 while (sum < target && end < nums.length) { sum += nums[end]; end++; } // 缩小左侧窗口直到窗口内的数组不符合条件 // 并同步更新最小值 while (sum >= target && start <= end) { res = Math.min(res, end - start); sum -= nums[start]; start++; } } return res == Integer.MAX_VALUE ? 0 : res; } }
还有比较复杂的滑动窗口题目,如 904. 水果成篮 76. 最小覆盖子串,这种滑动窗口问题下篇再谈。