LeetCode: 209. Minimum Size Subarray Sum

LeetCode: 209. Minimum Size Subarray Sum

题目描述

Given an array of ``n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

**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.

Follow up:

If you have figured out the O(n^2) solution, 
try coding another solution of which the time complexity is O(n log n). 

解题思路 —— 前序和+二分查找

先求得前序和,然后根据前序和,二分查找出满足要求的最短的连续子数组。

AC 代码

class Solution {
    // [beg, end)
    int binarySearch(const vector<int>& frontSum, int beg, int end, int target)
    {
        if(beg >= end) return beg;
        
        int mid = (beg+end)/2;
        if(frontSum[mid] == target) return mid;
        else if(frontSum[mid] > target) return binarySearch(frontSum, beg, mid, target);
        else return binarySearch(frontSum, mid+1, end, target);
    }
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if(nums.empty()) return 0;
        
        // 前序和
        vector<int> frontSum;
        for(int i = 0; i <= nums.size(); ++i)
        {
            if(i == 0) frontSum.push_back(0);
            else frontSum.push_back(nums[i-1]+frontSum.back());
        }
        
        int minLen = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            // 二分查找
            int idx = binarySearch(frontSum, i+1, frontSum.size(), frontSum[i]+s);
            if(idx < frontSum.size() && (minLen == 0 || minLen > idx-i))
            {
                minLen = idx -i;
            }
        }
        
        return minLen;
    }
};
全部评论

相关推荐

06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-15 17:24
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务