【LeetCode】滑动窗口相关算法题

1、介绍

滑动窗口算法是一种高效处理数组/字符串子序列化问题的技术，它通过维护一个动态的窗口来避免不必要的重复计算。

2、核心思想

1、窗口定义：使用两个指针表示当前考察的子序列
2、窗口移动：右指针扩张，扩大窗口范围，包含新元素；左指针收缩，缩小窗口范围，排除旧元素
3、状态维护：在窗口移动过程中维护关键状态信息

3、算法题

【1】长度最小的子数组

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

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

代码示例：

func minSubArrayLen(target int, nums []int) int {
	//左右边界初始为0，将最小长度初始设置为最大， 初始总和为0
	left, right, minLen, sum := 0, 0, math.MaxInt32, 0

	for right < len(nums) { //滑动右边界
		sum += nums[right] //计算总和

		for sum >= target { //总和大于目标值
			realLen := right - left + 1 //计算长度

			if realLen < minLen { //更新最小长度
				minLen = realLen
			}

			if realLen == 1 { //1就为最小长度，直接退出
				return 1
			}

			sum -= nums[left] //窗口左边界左移
			left++
		}

		right++ //窗口右边界右移
	}

	if minLen == math.MaxInt32 { //最小长度和初始值一样说明没有满足的情况
		return 0
	}

	return minLen
}