元宝 LeetCode 209. 长度最小的子数组 Java实现

LeetCode 209. 长度最小的子数组 Java 实现题目简述给定一个正整数数组“nums” 和目标值“target”找出和 ≥ target 的连续子数组中长度最小的那个返回其长度。如果不存在返回 0。思路滑动窗口双指针核心思想用两个指针“left” 和“right” 维护一个窗口“right” 不断右移把元素加入窗口和“sum”3. 当“sum target” 时尝试收缩左边界“left”尽可能缩小窗口4. 每次满足条件时更新最小长度[left … right]sum target → 收缩 leftJava 实现class Solution {public int minSubArrayLen(int target, int[] nums) {int left 0; // 窗口左边界int sum 0; // 窗口内元素和int minLen Integer.MAX_VALUE;for (int right 0; right nums.length; right) { sum nums[right]; // 扩张右边界 // 满足条件时尽量收缩左边界 while (sum target) { minLen Math.min(minLen, right - left 1); sum - nums[left]; left; } } // 没找到满足条件的子数组 return minLen Integer.MAX_VALUE ? 0 : minLen; }}复杂度分析维度 复杂度时间 O(n)“left” 和“right” 各遍历数组一次空间 O(1)只用常数个变量示例说明输入: target 7, nums [2,3,1,2,4,3]输出: 2解释: 子数组 [4,3] 和为 7长度最小为 2输入: target 4, nums [1,4,4]输出: 1解释: 单个元素 4 即满足输入: target 11, nums [1,1,1,1,1,1,1,1]输出: 0解释: 所有元素和也不够 11为什么不用前缀和 二分也可以用但滑动窗口更优方法 时间 适用场景滑动窗口 O(n) 数组全为正数本题满足前缀和 二分 O(n log n) 数组含负数时也适用本题数组元素全为正整数滑动窗口可以保证左指针只前进不后退因此是 O(n)。常见坑点循环条件是“while” 不是“if”收缩时要一直缩到不满足为止才能找到该右边界下的最小窗口返回前判断“minLen” 是否被更新过防止无满足条件的情况返回错误值数组全为正数是滑动窗口成立的前提如果含负数需要用前缀和 二分需要我再补充 前缀和 二分 的解法或者 Follow-up数组含负数怎么办 的处理思路吗