本文共 1959 字，大约阅读时间需要 6 分钟。

题目：

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.

For example, given the array [2,3,1,2,4,3] and s = 7,

the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

More practice:

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

解法：两种解法，时间复杂度分别是O(N)和O(N*log(N))。

O(N)解法

思路：

使用两个指针i,j，分别指向开头，然后移动一个指针i，直到两个指针之间的数据和sum大于等于s，此时标记两个之间的数据个数min_len=i-j+1，然后使后一个指针j往前移动，此时重新判断两个指针之间的数据和sum是否大于等于s，不是的话往前移动i，是的话往前移动j，在移动过程中，凡是遇到sum和大于等于s，就判断i-j+1是否小于min_len，如果是，就更新min_len。直到最后两个指针都到达队尾结束（两个指针都是从头到尾，复杂度O(N)）

class Solution {public:    int minSubArrayLen(int s, vector
   
    & nums) {        int len=nums.size();        int sum=0;        if(len==0) return NULL;        int i=-1,j=-1;        int min_len=INT_MAX;        bool flag=0;        while(i<=len-1&&j<=len-1)        {            if(sum>=s)            {                j++;                if(i-j+1
   

O(N*log(N))解法

题目非要整个N*log(N)的算法，好吧，就写个复杂点的，思路如下：

首先求出nums的累积分布和sums。

之后对sums的每个元素都进行遍历：sums[i] 如果sums[i]>=s，那么寻找使满足原数组中以i为结尾的，和大于等于s的最短连续序列的左下标。使用二分查找，复杂度是O(log(N)) 由于上述是一个一个遍历，复杂度是O(N)，所以总的复杂度是O(N*log(N))。

class Solution { public:    int minSubArrayLen(int s, vector
   
    & nums) {        int len=nums.size();        int sums[len+1]={
  0};        int min_len=INT_MAX,left=0;        for(int i=1;i<=len;i++)        {            sums[i]=sums[i-1]+nums[i-1];//累计求和        }        for(int i=0;i<=len;i++)         {            left=Calleftindex(sums,i,s);//寻找sums中以i为结尾的大于等于s的最短左下标，复杂度log(N)，二分查找            if(left!=INT_MAX&&i-left+1
    
     =s)             {                left=mid+1;                if(left>=max_left)                    max_left=left;            }            else            {                right=mid-1;            }       }        return max_left;    }};
    
   

转载地址：http://jexvi.baihongyu.com/