首页 > 其他 > 详细

[刷题] LeetCode 209 Minimum Size Subarray Sum

时间:2020-03-30 10:12:15      阅读:87      评论:0      收藏:0      [点我收藏+]

要求

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

示例

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

思路

  • 暴力解法(n3)
  • 滑动窗口()

技术分享图片

 

技术分享图片
 1 class Solution{
 2 public:
 3     int minSubArrayLen(int s, vector<int>& nums){
 4         int l = 0, r = -1;
 5         int sum = 0;
 6         int res = nums.size() + 1;
 7         
 8         while( l < nums.size())    {
 9             if( r+1 < nums.size() && sum < s)
10                 sum += nums[++r];                    
11             else
12                 sum -= nums[l++];
13             if(sum >= s)
14                 res = min(res,r-l+1);
15         }        
16         if(res== nums.size()+1)
17             return 0;
18         return res;
19     }
20 };
View Code

延伸

  • 双索引技术

[刷题] LeetCode 209 Minimum Size Subarray Sum

原文:https://www.cnblogs.com/cxc1357/p/12585766.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!