首页 > 其他 > 详细

209. Minimum Size Subarray Sum

时间:2020-03-21 14:24:25      阅读:53      评论:0      收藏:0      [点我收藏+]

问题:求给定数列中,最短子数列,使子数列之和>=给定值s

Example: 
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

  

方法:

滑动窗口,

移动窗口右边,顺序递加nums[i],直到sum>=s

移动窗口左边,逐次去掉左边的值,求的满足sum>=s的最小个数cout,

再使用一个变量res,记录每次满足条件的cout的最小值,res=min(res, cout)

 

代码参考:

 1 class Solution {
 2 public:
 3     int minSubArrayLen(int s, vector<int>& nums) {
 4         int i=0;
 5         int sum=0;
 6         int cout=0;
 7         int res=INT_MAX;
 8         for(i=0;i<nums.size();i++){
 9             sum+=nums[i];
10             cout++;
11             while(sum>=s){
12                 res=min(res, cout);
13                 sum-=nums[i-cout+1];
14                 cout--;
15             }
16             
17         }
18         if(res>nums.size())return 0;
19         return res;
20     }
21 };

 

209. Minimum Size Subarray Sum

原文:https://www.cnblogs.com/habibah-chang/p/12538974.html

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