目录1. 题目解析示例 1示例 22. 算法原理解法一暴力枚举所有子数组的和 —— O(n²)解法二利用单调性使用“同向双指针”来优化 —— O(n)✅ 怎么用图解过程正确性时间复杂度3. 编写代码OJ链接 https://leetcode.cn/problems/minimum-size-subarray-sum/description/1. 题目解析本题来自 LeetCode 第 209 题长度最小的子数组。题目描述给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其和 ≥target的长度最小的连续子数组[nums[l], nums[l1], ..., nums[r-1], nums[r]]并返回其长度。如果不存在符合条件的子数组返回0。示例 1输入target 7, nums [2,3,1,2,4,3] 输出2 解释子数组 [4,3] 是该条件下长度最小的子数组。示例 2输入target 4, nums [1,4,4] 输出1关键点子数组必须是连续的要求和≥ target返回的是最小长度不是子数组本身若不存在返回02. 算法原理解法一暴力枚举所有子数组的和 —— O(n²)通过双重循环枚举所有子数组计算和并比较时间复杂度为 O(n²)在数据规模大时会超时。解法二利用单调性使用“同向双指针”来优化 —— O(n)这是本题的核心解法滑动窗口Sliding Window✅ 怎么用我们用两个指针left和right构建一个窗口窗口内的元素和记为sum窗口长度记为len。步骤如下初始化left 0,right 0进窗口 →right向右移动将nums[right]加入sum判断 → 如果sum target说明当前窗口满足条件尝试缩小窗口更新最小长度len min(len, right - left 1)出窗口 →left向右移动sum - nums[left]重复步骤 2~3直到right遍历完整个数组图解过程以target 7, nums [2,3,1,2,4,3]为例初始left0, right0, sum0, len∞right0→ 进窗口sum2→ 不满足right1→ 进窗口sum5→ 不满足right2→ 进窗口sum6→ 不满足right3→ 进窗口sum8→ 满足→ 更新len4出窗口sum6, left1right4→ 进窗口sum10→ 满足→ 更新len4当前窗口 [3,1,2,4]出窗口sum8, left2right5→ 进窗口sum11→ 满足→ 更新len3[1,2,4]出窗口sum7, left3right5→ 再次判断sum7 7→ 更新len2[2,4]出窗口sum3, left4循环结束✅ 最终最小长度为2正确性利用单调性规避了很多没有必要的枚举行为因为数组元素都是正整数所以当sum target时我们移动left指针一定能缩小窗口且不会错过更优解。这是滑动窗口能成立的核心前提。时间复杂度right指针遍历数组一次 → O(n)left指针也最多移动 n 次 → O(n)总体O(n)✅ 从 nn → 2n → O(n)线性时间复杂度非常高效3. 编写代码以下是 Java 实现代码class Solution { public int minSubArrayLen(int target, int[] nums) { int n nums.length, sum 0, len Integer.MAX_VALUE; for (int left 0, right 0; right n; right) { sum nums[right]; // 进窗口 while (sum target) { // 判断 len Math.min(len, right - left 1); // 更新结果 sum - nums[left]; // 出窗口 } } return len Integer.MAX_VALUE ? 0 : len; } }可直接复制运行。欢迎在评论区留言交流我们一起把滑动窗口吃透OJ链接 https://leetcode.cn/problems/minimum-size-subarray-sum/description/祝你刷题顺利早日拿Offer点个关注
