209.长度最小的子数组

清疚 2024-03-17 19:39 82阅读 0赞

#### 209.长度最小的子数组 ####

*  题干
 *  具体思路
 *  易错点
 *  代码实现

## 题干 ##

[leetcode 209.长度最小的子数组 答题入口][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.  用一个循环来表示滑动窗口的结束位置索引的变化
2.  用一个while循环来缩减滑动窗口的开始位置

## 易错点 ##

1.  注意while循环的条件是sum>=target，因为每次满足大于等于条件后需要进入循环，更新len的值。
2.  注意while循环中两条语句的先后顺序。
3.  通过滑动窗口方式，将易想思路的O(n^2)时间复杂度缩减到O(N)。

## 代码实现 ##

理解思路后我的版本：

public int minSubArrayLen(int target, int[] nums) {
        
            int len = Integer.MAX_VALUE;
            int i = 0, sum = 0;
            for(int j = 0; j < nums.length; j++){
        
                sum += nums[j];
                while(sum >= target){
        
                    len = Math.min(j-i+1, len);
                    sum -= nums[i++];
                }
            }
            if(len == Integer.MAX_VALUE)
                return 0;
            else
                return len;
        }

代码随想录版本：

public int minSubArrayLen(int target, int[] nums) {
        
            int len = Integer.MAX_VALUE;
            int i = 0, sum = 0;
            for(int j = 0; j < nums.length; j++){
        
                sum += nums[j];
                while(sum >= target){
        
                    len = Math.min(j-i+1, len);
                    sum -= nums[i++];
                }
            }
            return len == Integer.MAX_VALUE ? 0 : len;
        }

**参考资料**：[209.长度最小的子数组][209.]

[leetcode 209._]: https://leetcode.cn/problems/minimum-size-subarray-sum/description/
[209.]: https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html#%E7%9B%B8%E5%85%B3%E9%A2%98%E7%9B%AE%E6%8E%A8%E8%8D%90