209. 长度最小的子数组

问题

给定一个含有 \(n\) 个正整数的数组和一个正整数 \(s \),找出该数组中满足其和 \(≥ s \)的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回\( 0\)。

示例:

输入: \(s = 7, nums = [2,3,1,2,4,3]\)
输出: \(2\)
解释: 子数组 \([4,3]\) 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了\(O(n)\) 时间复杂度的解法, 请尝试\( O(n log n)\) 时间复杂度的解法。

解法

连续子数组,考虑使用双指针\(start\)与\(end\)滑动窗口来判断.设置一个\(sum\)值,表示滑动窗口中的和,每一轮循环,判断\(sum\)与\(s\)的关系,有两种情况:

  • \(sum\)大于等于\(s\),此时\(sum\)减去\(start\)指针所指向的值,\(start\)指针前进。
  • \(sum\)小于\(s\),此时,\(sum\)加上\(end\)的值,\(end\)指针前进。

代码

java实现

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        // 注意这里的end的起始位置
        int start = 0, end = -1;
        int result = Integer.MAX_VALUE, sum = 0;
        // 开始循环,循环跳出的条件是start指针循环到数组尾部了
        while (start < nums.length) {
            // 这里需要注意判断条件
            if (sum < s && end + < nums.length) {
                end++;
                sum += nums[end];            
            } else {
                sum -= nums[start];
                start++;
            }
            if (sum >= s) result = result < end - start + 1 ? result : end - start + 1;
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}