leetcode-209. 长度最小的子数组

   日期:2020-07-11     浏览:90    评论:0    
核心提示:给定一个含有n个正整数的数组和一个正整数s ,找出该数组中满足其和≥ s的长度最小的子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。示例:输入:s = 7, nums = [2,3,1,2,4,3]输出:2解释:子数组 [4,3] 是该条件下的长度最小的子数组。解:滑动窗口public static int minSubArrayLen(int s, int[] nums) { int len = nums.length; if ...

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

示例:

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

解:滑动窗口

public static int minSubArrayLen(int s, int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int left = 0, right = 0, sum = 0;
        int res = Integer.MAX_VALUE;
        // 右指针小于数组长度
        while (right < len) {
            // 每次加右侧一个数字求和
            sum += nums[right++];
            // 和大于等于预期值,并且符合当前窗口规则
            while(sum >= s && left <= right) {
                // 上次计算结果和本次计算结果取最小值
                res = Math.min(res, right - left);
                // 根据题意1为最少子数组,所以可以提前结束
                if (res == 1) {
                    return 1;
                }
                // 缩小左侧窗口
                sum -= nums[left++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

 

 
打赏
 本文转载自:网络 
所有权利归属于原作者,如文章来源标示错误或侵犯了您的权利请联系微信13520258486
更多>最近资讯中心
更多>最新资讯中心
0相关评论

推荐图文
推荐资讯中心
点击排行
最新信息
新手指南
采购商服务
供应商服务
交易安全
关注我们
手机网站:
新浪微博:
微信关注:

13520258486

周一至周五 9:00-18:00
(其他时间联系在线客服)

24小时在线客服