209. Subarray with the smallest length (array)

  subject ：

Given a containing  n  An array of positive integers and a positive integer  s , Find the sum of the array ≥ s The smallest length of continuity Subarray , And return its length . If there is no sub array that meets the conditions , return 0.

Example ：

Input ：s = 7, nums = [2,3,1,2,4,3] Output ：2 explain ： Subarray  [4,3]  Is the smallest subarray in this condition .

Method 1 ： Violence solution

public int minSubArrayLen(int s,int[] nums){
    int n = nums.length;
    // Sum of subsequences 
    int sum =0;
    // Subsequence length 
    int subLength =0;
    int res = Integer.MAX_VALUE;
        for (int i = 0; i <n ; i++) {
            // Set the starting point of the subsequence 
            sum=0;
            for (int j = i; j <n ; j++) {
                // Set the end point of the subsequence 
                sum+=nums[j];
                if(sum >=s){
                    // Update subsequence length 
                    subLength = j-i+1;
                    res = Math.min(res, subLength);
                    break;// If you find the minimal array , Jump out of the second loop that sets the end point of the subsequence , Add the starting point of subsequence and continue to traverse 
                }
            }
        }
        // If res If it's not assigned , Just go back to 0, There are no subsequences that meet the conditions 
        return res == Integer.MAX_VALUE ? 0:res;
    }

Time complexity ：O（n^2）

Spatial complexity ：O（1）

Method 2 ： The sliding window （ Double pointer ）

Ideas ： Use the left and right pointers to dynamically maintain and update the data s The smallest subarray of

// Method 2 ： The sliding window （ Double pointer ）
    public int minSubArrayLen(int s,int[] nums){
        // The length of the array 
        int n = nums.length;
        // Sum of subsequences 
        int sum = 0;
        // Subsequence length 
        int subLength = 0;
        // Subsequence results 
        int result = Integer.MAX_VALUE;
        // Slide window start position 
        int left =0;
        for (int right=0;right<n;right++) {
            sum+= nums[right];
            while (sum>=s){
                subLength = right-left+1;
                result = Math.min(result, subLength);
                sum-=nums[left++];
            }
        }
        return result==Integer.MAX_VALUE? 0: result;
    }

Time complexity ：O（n）

Spatial complexity ：O（1）

Why? for Nested inside the loop while The cycle time complexity is O（n）？

Because time complexity measures the number of repetitions of each element , In the sliding window , The element appears once when entering the window , Appears once when leaving the window . So each element is manipulated twice , The time complexity should be O（2n）, That is to say O（n） 了 .