LC209 长度最小的子数组

怎样从“target = 7, nums = [2,3,1,2,4,3]”推导出 滑动窗口 · 变长，并证明每次状态变化都不会漏掉答案？

中心结论：右指针扩张累加 sum；一旦 sum ≥ target 就连续左缩，每次缩之前先记录当前长度。

给定一个整型数组和一个数字 s，找到数组中最短的一个连续子数组，使得连续子数组的数字之和 sum>=s，返回最短的连续子数组的返回值。

在本站主例中，target = 7, nums = [2,3,1,2,4,3]

算法最终需要得到或观察：最短子数组是 [4,3]，长度 2。

枚举所有子串会反复统计大量相同字符；窗口只处理右端新加入和左端刚移出的增量。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“伸缩窗口”，明确答案需要观察什么。
2. 2状态只维护 窗口左界 L、右界 R、窗口和 sum、当前最短长度 best。
3. 3转移每一步按照 右指针扩张累加 sum；一旦 sum ≥ target 就连续左缩，每次缩之前先记录当前长度。
4. 4收尾读取 最短子数组是 [4,3]，长度 2。，并复核边界与复杂度。

右端扩张负责获得新信息，左端收缩负责恢复合法性。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：窗口左界 L、右界 R、窗口和 sum、当前最短长度 best。

这一题的解题思路是用滑动窗口。在滑动窗口 [i,j]之间不断往后移动，如果总和小于 s，就扩大右边界 j，不断加入右边的值，直到 sum > s，之和再缩小 i 的左边界，不断缩小直到 sum < s，这时候右边界又可以往右移动。以此类推。

右指针扩张累加 sum；一旦 sum ≥ target 就连续左缩，每次缩之前先记录当前长度。

执行过程中持续维护：窗口左界 L、右界 R、窗口和 sum、当前最短长度 best。

正确性依赖以下不变量：元素均为正：右扩 sum 单调增、左缩 sum 单调减，滑窗才成立。

面试时可以压缩为：元素都是正数，右扩 sum 增、左缩 sum 减。右指针扩张，sum≥target 时尽量收缩左边界并记录长度；每个元素进出窗口各一次，O(n)。

落到当前题，执行机制可以压缩为：右指针扩张累加 sum；一旦 sum ≥ target 就连续左缩，每次缩之前先记录当前长度。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入target = 7, nums = [2,3,1,2,4,3] 因为：右指针扩张累加 sum；一旦 sum ≥ target 就连续左缩，每次缩之前先记录当前长度。
2. 2右扩：加入 nums[1] = 3右指针纳入 nums[R]=3，窗口和增加到 5。还不够。 因为：正整数右扩只会让 sum 变大，逐步逼近 target。
3. 3右扩：加入 nums[3] = 2右指针纳入 nums[R]=2，窗口和增加到 8。达标！ 因为：正整数右扩只会让 sum 变大，逐步逼近 target。
4. 4右扩：加入 nums[4] = 4右指针纳入 nums[R]=4，窗口和增加到 10。达标！ 因为：正整数右扩只会让 sum 变大，逐步逼近 target。
5. 5左缩：移出 nums[1] = 3左指针右移，把 nums[1]=3 移出窗口。仍然达标，继续尝试缩短。 因为：收缩到 sum < target 才停；再缩就不合法了，所以当前长度是这一轮的下界。
6. 6右扩：加入 nums[5] = 3右指针纳入 nums[R]=3，窗口和增加到 9。达标！ 因为：正整数右扩只会让 sum 变大，逐步逼近 target。
7. 7sum=7 ≥ 7，窗口长度=2窗口和达标，先记录长度 2（刷新最短记录），再试着从左边收缩。 因为：已达标时收缩可能得到更短的合法窗口，所以要尽量缩到不再合法为止。
8. 8收尾与复杂度最短子数组是 [4,3]，长度 2。 因为：时间 O(n) · 空间 O(1)。右指针扩张累加 sum；一旦 sum ≥ target 就连续左缩，每次缩之前先记录当前长度。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func minSubArrayLen(target int, nums []int) int {
	left, sum, res := 0, 0, len(nums)+1
	for right, v := range nums {
		sum += v
		for sum >= target {
			res = min(res, right-left+1)
			sum -= nums[left]
			left++
		}
	}
	if res == len(nums)+1 {
		return 0
	}
	return res
}

func min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

func main() {
    // 1. 主例
    //    输入：mode="min-subarray", array=[2,3,1,2,4,3], target=7
    //    期望：最短子数组是 [4,3]，长度 2。
    //
    // 2. 失败 / 未命中
    //    检查：数组含负数时本解法失效；本题前提是正整数。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC3 无重复字符最长子串；LC76 最小覆盖子串
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意target = 7, nums = [2,3,1,2,4,3]
2. 2重复枚举所有子串会反复统计大量相同字符；窗口只处理右端新加入和左端刚移出的增量。
3. 3优化右指针扩张累加 sum；一旦 sum ≥ target 就连续左缩，每次缩之前先记录当前长度。
4. 4证明元素均为正：右扩 sum 单调增、左缩 sum 单调减，滑窗才成立。
5. 5复杂度时间 O(n)，空间 O(1)