专栏首页chenjx85的技术专栏leetcode-209-长度最小的子数组

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

题目描述:

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

示例: 

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

进阶:

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

要完成的函数:

int minSubArrayLen(int s, vector<int>& nums) 

说明:

1、这道题给定一个正整数s,和一个包含正整数的vector,要求在vector中找到最短长度的连续子数组,这个子数组中所有数的和>=s,返回子数组的长度。

2、这道题不会很难,我们用滑窗的方法找到和>=s的子数组,接着不断更新最短的长度,最终返回这个最短的长度即可。

最后要考虑一下边界情况,也就是当滑窗到达vector末尾了怎么处理,和vector中没有元素的情况。

代码如下:(附详解)

    int minSubArrayLen(int s, vector<int>& nums) 
    {
        if(nums.empty())return 0;//vector中没有元素,找不到满足条件的子数组,返回0
        int start=0,end=0,s1=nums.size(),sum=nums[0],record=INT_MAX;//start表示滑窗的开端,end表示滑窗末端
        while(start<s1)//对开端在vector中的每个位置,都进行考虑
        {
            while(sum<s)//当和小于s时,末端不断向右走,sum也不断地加
            {
                end++;
                if(end==s1)//如果超出vector的长度,那么当前滑窗不满足条件的,这个时候也就可以返回record了
                    return record==INT_MAX?0:record;//如果record等于初始值,那么必然没有改变过record,也就是从头到尾都没找到满足条件的滑窗
                sum+=nums[end];
            }
            record=min(record,end-start+1);//更新record
            sum-=nums[start];//减去开端
            start++;//开端到了下一位
        }
        return record;
        
    }

上述代码实测8ms,beats 98.44% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-53-Maximum Subarray(动态规划详解)

    chenjx85
  • leetcode-674-Longest Continuous Increasing Subsequence

    chenjx85
  • leetcode-628-Maximum Product of Three Numbers

    chenjx85
  • LeetCode题组:第26题-删除排序数组中的重复项

    给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。(注意这里提到了排序数组,也就是说数组是有序的。如果无序,...

    明天依旧可好
  • 100. 删除排序数组中的重复数字 双指针+替换

    给定一个排序数组,在原数组中删除重复出现的数字,使得每个元素只出现一次,并且返回新的数组的长度。 不要使用额外的数组空间,必须在原地没有额外空间的条件下完成。...

    和蔼的zhxing
  • 去除有序数组中重复元素的 3 种方法,快来瞧瞧吧

    给定一个有序数组,要删除数组重复出现的元素,使得每个元素之出现一次,然后返回移除重复数组后的新长度;

    村雨遥
  • LeetCode 26 Remove Duplicates from Sorted Array

    一份执着✘
  • LeetCode第一题

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    杨小杰
  • leetcode410. Split Array Largest Sum

    将一个长度为n的正整数数组分割为m个非空的连续子数组,并分别计算每个子数组中所有元素的和。求一种分割方式,使得该分割方式生成的最大子数组和为所有分割方式中最小的...

    眯眯眼的猫头鹰
  • Dimple在左耳听风ARTS打卡(第九期)

    所谓ARTS: 每周至少做一个LeetCode的算法题;阅读并点评至少一篇英文技术文章;学习至少一个技术技巧;分享一篇有观点和思考的技术文章。(也就是Algor...

    程序员小跃

扫码关注云+社区

领取腾讯云代金券