【Leetcode 209】长度最小的子数组 —— 滑动窗口|双指针

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

题目分析

我们可以使用双指针解决本题，定义两个指针 i 和 j 分别表示子数组（滑动窗口窗口）的开始位置和结束位置，维护变量 sum 存储子数组中的元素和。

每一轮迭代中，每当 sum >= target 则记录子数组最小长度，移动慢指针。在每一轮迭代最后，移动快指针

双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息

经典双指针的数组遍历，更多案例可见 Leetcode 双指针详解

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