C++,O(n), easy to understand:)


  • 4
    C
    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            const int n = nums.size();
            int left = 0, right = 0, sum = 0, result = INT_MAX;
            while (right < n) {
                while (right < n && sum < s) {  // expend [left,right] to make sum >= s, notice that right is just at right of index where sum >= s;
                    sum += nums[right];
                    ++right;
                }
                while (left < right && sum >= s) {   // shrink [left, right] to make  it  as small as possible
                    result = min(result, right - left);  // there we don't use right - left + 1, because right is just at right of index where sum >= s;
                    sum -= nums[left];
                    ++left;
                }
                
            }
            
            return result == INT_MAX ? 0 : result;
        
        }
    };

Log in to reply
 

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