Simple c++ O(n) solution, AC


  • 0
    L
    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            
            if(nums.size()==0) return 0;
            int length = 0;
            vector<int> sums;
            
            for(int i=0; i<nums.size(); i++) {
                
                if (nums[i]>s) return 1;
                
                if (i == 0) sums.push_back(nums[i]);
                else sums.push_back(sums[i-1] + nums[i]);
                
                if(sums[i]<s) continue;
                else {
                    if(length==0) {
                        length = i+1;
                    } 
                    int j = i - length + 1;
                    while(sums[i] - sums[j]>=s && j<i) j++;
                    length = length < i-j+1 ? length : i-j+1;
                }
            }
            
            return length;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.