Skip to content

Latest commit

 

History

History
43 lines (38 loc) · 1.61 KB

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

File metadata and controls

43 lines (38 loc) · 1.61 KB

209 长度最小的子数组

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

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

思路:滑动窗口法
当输出或比较的结果在原数据结构中是连续排列的时候,可以使用滑动窗口算法求解。
将两个指针比作一个窗口,通过移动指针的位置改变窗口的大小,观察窗口中的元素是否符合题意。

初始窗口中只有数组开头一个元素。 当窗口中的元素小于目标值,右指针向右移,扩大窗口。 当窗口中的元素大于目标值,比较当前窗口大小是否为最小值,左指针向右移,缩小窗口。

代码:

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if(nums == null)
            return 0;
        int minlength = Integer.MAX_VALUE;
        //left和right分别代表滑动窗口的左右端
        int left = 0;
        int right = 0;
        int sum = 0;
        while(right < nums.length){
            sum += nums[right];
            right++;
            //和sum大于目标值s时,left左移,滑动窗口缩小
            while(sum >= s){
                minlength = Math.min(minlength, right - left );
                sum -= nums[left];
                left++;
            }
        }
        return minlength == Integer.MAX_VALUE? 0:minlength;
    }
}