【LeetCode】209.长度最小的子数组

1 问题

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [$nums_l$, $nums_{l+1}$, …, $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

示例 3

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

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

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(nlog(n)) 时间复杂度的解法。

2 解题思路

2.1 暴力

2.2 滑动窗口

套用公式：

初始化将滑动窗口压满，取得第一个滑动窗口的目标值；

继续滑动窗口，每往前滑动一次，需要删除一个和添加一个元素。

• 初始化左右指针 left，right，计算第一个sum；
• 当sum>=target时，调整窗口。计算当前连续数组长度，并比较历史最小值，然后收缩窗口，sum-=nums[left++]。

3 代码

class Solution {
    //滑动窗口
    //1.初始化，计算sum
    //2.当sum>=target时，调整窗口，收缩。计算当前连续数组长度，并比较历史最小值，然后收缩窗口，sum-=nums[left++]
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;

        for (; right < nums.length; right++) {
            sum += nums[right];
            //判断
            while (sum >= target) {
                if (minLen > right - left + 1) {
                    minLen = right - left + 1;
                }
                sum -= nums[left++];
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
}