Sliding Window Solution


  • 0
    T
    class Solution {
        //Sliding window Algorithm: O(n)
        //use two pointers, which are left and right, to keep track of the sub array
        //If the sum of this sub array is smaller than s, shift right pointer
        //O/w update the minSize if the value of (right - left + 1) is no bigger than it. 
        public int minSubArrayLen(int s, int[] nums) {
            int left = 0, right = 0;
            int sum = 0;
            int length = nums.length;
            boolean exist = false;
            while(right < nums.length){
                sum += nums[right];
                if(sum >= s){
                    exist = true;
                    length = Math.min(right - left + 1, length);
                    
                    //left pinter silding...
                    sum -= nums[left];
                    left++;
                    while(sum >= s){
                        length = Math.min(right - left + 1, length);
                        sum -= nums[left];
                        left++;
                    }
                }
                right++;
            }
            
            if(!exist){
                return 0;
            }
            else{
                return length;
            }
        }
    }
    

Log in to reply
 

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