力扣209长度最小的子数组-java

题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

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

做法:双指针-滑动窗口

什么是滑动窗口?
不断的调节子序列的起始位置和终止位置,进而得出想要的结果。

算法步骤

第一步:right向右移增加窗口,直到窗口内的数字和大于等于S
第二步:记录这个时候的长度,left向右移动,开始减少长度,每减少一次,就更新最小长度,直到窗口内的数小于s

举个栗子
力扣209长度最小的子数组-java
这个时候窗口内所有数字的和只有 2 这个数字,2 小于 7 ,rigth 右移。
力扣209长度最小的子数组-java
这个时候窗口内的数字是 2 3,2 +3 = 5 小于 7 ,rigth 右移
力扣209长度最小的子数组-java
这个时候窗口内的数字是 2 3 1 ,2 +3 +1= 6 小于 7 ,rigth 右移
力扣209长度最小的子数组-java
这个时候窗口内的数字是 2 3 1 2 ,2 +3 +1+2= 8 大于 7 ,记录这个时候的长度 min = 4,left 右移
力扣209长度最小的子数组-java
这个时候窗口内的数字是 3 1 2 ,3 +1+2= 6 小于 7 ,rigth 右移
力扣209长度最小的子数组-java
这个时候窗口内的数字是 3 1 2 4 ,3 +1+2+4= 10 大于 7 , 更新长度 min = 4,left 右移
力扣209长度最小的子数组-java
这个时候窗口内的数字是 1 2 4 ,1+2 +4= 7 等于 7 更新长度 min = 3,left 右移
力扣209长度最小的子数组-java
这个时候窗口内的数字是 2 4 ,2 + 4= 6 小于 7 ,rigth 右移
力扣209长度最小的子数组-java
这个时候窗口内的数字是 2 4 3,2 +4 + 3= 9 大于 7 更新长度 min = 3,left 右移
力扣209长度最小的子数组-java
这个时候窗口内的数字是 4 3,4 + 3= 7 等于 7 更新长度 min = 2,left 右移
力扣209长度最小的子数组-java
这个时候窗口内的数字是 3, 3 小于 7,rigth右移这个循环结束

class Solution {
   public int minSubArrayLen(int s, int[] nums) {
  
    if(nums == null || nums.length == 0) return 0;
        int left = 0;//左指针
        int right = 0;//右指针
        int sum = 0;//滑动窗口数值的和
        int min = Integer.MAX_VALUE;
        //滑动窗口的长度,这里的 Integer.MAX_VALUE;是Integer.MAX_VALUE表示int数据类型的最大取值数:2 147 483 647
        while (right < nums.length) {
            sum += nums[right];//计算滑动窗口内数字的和
            right++;
            //每次更新起始位置,并不断比较子序列是否符合条件
            while (sum >= s) {
                min = Math.min(min, right - left);//取子序列的长度
                sum -= nums[left];//这里体现了滑动窗口的精髓之处,不断的变更
                left++;
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
        //三元表达式,如果没有符合条件的子序列返回0,否则就是找到了子序列,返回长度
        }   
}

参考:
https://mp.weixin.qq.com/s?__biz=MzUxNjY5NTYxNA==&mid=2247484315&idx=1&sn=414b885abba34abfd8d9f35c9f61b857&scene=21#wechat_redirect

上一篇:【Leetcode】209. 长度最小的子数组(Minimum Size Subarray Sum)


下一篇:学习slam遇到的问题 之 ROS安装