算法-滑动窗口 2024-04-13 默认分类 暂无评论 696 次阅读 [209. 长度最小的子数组](https://leetcode.cn/problems/minimum-size-subarray-sum/) 给定一个含有 `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` ```Go func minSubArrayLen(target int, nums []int) int { len := len(nums) ans := len + 1 s := 0 left := 0 for right, n := range nums { s += n for s-nums[left] >= target { s -= nums[left] left++ } if s >= target { ans = min(ans, right-left+1) } } if ans == len+1 { return 0 } else { return ans } } ```   算法思想: 1.先扩展 (扩展至满足要求) 2.收缩 (贪心策略, 缩至最小) 右端点不断向右侧移动 左端点缩到最小 标签: 算法 转载请注明文章来源 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭