C++ 6ms solution sliding window


  • 17
    C

    Any elegant way to replace do-while loop ? Look like it's the most fitting....

    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int num_len= nums.size();
            int left=0, right=0, total=0, min_len= num_len+1;
            while (right < num_len) {
                // move right silder forward till total >= s
                do { total += nums[right++]; } while (right<num_len && total< s);
                // move left slider forward while maintaining total >= s
                while (left<right && total-nums[left]>=s) total -= nums[left++];
                // record if it's the minimum
                if (total>=s && min_len> right- left) 
                    min_len= right- left;
            }
            return min_len<=num_len ? min_len: 0;
        }
    };

  • 0
    L

    Nice to know this is sliding window algorithm, thanks.


  • 0

    Great idea! Very easy to understand and to prove it is O(n).


  • 0
    9
    int minSubArrayLen(int s, int* nums, int n) {
        if (n < 1)
        {
            return 0;
        }
            
        int result = n+1;
        
        int sum = 0;
        int left = 0;
        int right = 0;
    
        while (right < n)   
        {
            sum += nums[right];
            if (sum >= s)
            {
                while (sum >= s)
                {
                    sum -= nums[left];
                    left++;
                }   
                // left-1...right保存了此时最短的和大于s的序列
                
                int temp = right-left+2;
                if (temp < result)
                {
                    result = temp;
                }
            }
            right++;
        }
    
        if (result > n)
        {
            return 0;
        }
    
        return result; 
    }

  • 0
    X

    what about if num_len==int_max?
    num_len+1 will overflow


  • 0
    C

    For large arrays (size() > INTMAX) you may have to rethink the container sizes. At a quick glance just by upgrading all variables to long seems to work. min_len= num_len+1; is used as a sentinel to indicate an invalid min_len for the final return statement.


  • 0

    nice!!!!!!!!


Log in to reply
 

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