滑动窗口算法-leetcode209.长度最小的子数组
滑动窗口算法概述
滑动窗口算法是一种用于处理数组、字符串等序列数据结构的优化技术。它通过维护一个窗口（通常是一个子数组或子字符串），并在序列上滑动这个窗口来解决问题。该算法可以将嵌套的循环问题转换为单循环问题，从而降低时间复杂度。
基本思想
设定两个指针，左指针（left）和右指针（right），这两个指针定义了一个窗口。窗口内的数据结构可以是数组的一个子区间、字符串的一个子串等。
右指针向右移动用于扩展窗口，将元素纳入窗口范围，直到满足某种条件（例如窗口内元素的和达到某个值、包含了特定的字符等）。
左指针向右移动用于收缩窗口，将元素排除在窗口范围之外，同时保持窗口满足特定的性质。
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组
[numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
在本题中实现滑动窗口，主要确定如下三点：
- 窗口内是什么？
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。 - 如何移动窗口的起始位置？
窗口的起始位置如何移动：如果当前窗口的值大于等于s了，窗口就要向前移动了（也就是该缩小了）。 - 如何移动窗口的结束位置？
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
package main
import "fmt"
func main() {
// 定义一个整数切片nums，包含了一些整数元素
nums := []int{2, 3, 1, 2, 4, 3}
// 定义目标值target
target := 7
// 调用minSubArrayLen函数，传入nums和target，获取满足条件的最小子数组长度
result := minSubArrayLen(nums, target)
// 打印结果
fmt.Println(result)
}
// minSubArrayLen函数用于找出给定整数切片nums中，其元素和大于等于目标值target的最小子数组长度
func minSubArrayLen(nums []int, target int) int {
// 初始化左指针left，指向子数组的起始位置，初始化为0
left, right, sum := 0, 0, 0
// 初始化result为切片nums的长度加1，这是一个初始的较大值，用于后续比较找到更小的长度
result := len(nums) + 1
// 开始遍历整数切片nums，通过移动右指针right来扩展窗口
for ; right < len(nums); right++ {
// 将右指针right指向的元素累加到sum中，即不断扩大窗口内元素的和
sum += nums[right]
// 当窗口内元素的和sum大于等于目标值target时，进入内层循环
for sum >= target {
// 计算当前满足条件的子数组的长度
length := right - left + 1
// 如果当前长度小于之前记录的result，更新result为更小的长度
if length < result {
result = length
}
// 将左指针left指向的元素从sum中减去，即开始收缩窗口，尝试找到更小的满足条件的子数组
sum -= nums[left]
// 左指针left向右移动一位，继续收缩窗口的操作
left++
}
}
// 如果最终result的值仍然是切片nums的长度加1，说明没有找到满足条件的子数组，返回0
if result == len(nums)+1 {
return 0
}
// 返回满足条件的最小子数组长度
return result
}
原文地址：https://blog.csdn.net/qq_51537858/article/details/143769735
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！