前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 209. Minimum Size Subarray Sum

LeetCode 209. Minimum Size Subarray Sum

作者头像
我有一只萌妹子
发布2022-06-23 13:59:55
1320
发布2022-06-23 13:59:55
举报
文章被收录于专栏:编程碎碎念编程碎碎念

解法一

 使用滑动窗口的方式进行求解,在[ i...j]之前滑动:

  当前的sum < s 时,j++ 窗口增大,并更新

  sum >=s 时,i++,缩小窗口。

代码语言:javascript
复制
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
            return 0;
        int i = 0,j = -1 ;   //[i..j] is sliding window
        int res = n +1;
        int sum = 0;
        
        
        while(i < n){
            if( j+1 < n && sum < s ){
                sum += nums[++j];
            }else{
                 sum = sum - nums[i++];
            }
            if (sum >= s)
                res = min( res , j-i+1 );   //update now length 
        }
        
        if(res == n+1)   // 
            return 0;
        return res;
    }
};

解法二:

题目中提到,可以思考一种 nlogn 的解放,经过思考发现可以使用二分搜索的方式进行求解,以长度为8为例,先用一个长度为4的窗口从左到右滑动一遍,如果有满足条件的,用长度为2的再进行滑动,如果没有则用长度为6的。以此类推,在此只给出思路。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-03-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档