C++ code, you can imagine this problem as sliding window


  • 0
    Y

    I don't like concise code, they always make people puzzled.

    So this code is not concise anymore, but I think it's clear enough to understand.

    /*TESTCASE:
    1. [2,3,1,2,4,3] s=7 
    2. [1,1,1,1] s = 5
    3. [1,4,4] s=4
    */
    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int arrSize = nums.size();
            int lenMin = arrSize;
            int startPosition = 0, endPosition = 0;
            int sum = 0;
            /* create a window */
            while(endPosition<arrSize && sum<s)
                sum += nums[endPosition++];
            if(sum<s) return 0;
            adjustWindow(nums,s,sum,startPosition,endPosition,lenMin);
            
            /*slide the window*/
            while(endPosition < arrSize){
                sum = sum - nums[startPosition] + nums[endPosition];
                startPosition++;
                endPosition++;
                if(sum>=s)
                    adjustWindow(nums,s,sum,startPosition,endPosition,lenMin);
            }
            return lenMin;
        }
    private:
        void adjustWindow(const vector<int>& nums, const int& s, int& sum, int& startPosition, const int& endPosition, int& lenMin){
            /* this function will change the `startPosition`, `lenMin`, and `sum` */
            while(startPosition<endPosition && sum-nums[startPosition]>=s)
                        sum -= nums[startPosition++];
            lenMin = min(endPosition-startPosition,lenMin);
        }
    };

Log in to reply
 

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