Array -- 209. Subarray with the smallest length

1 Title Description

209. Subarray with the smallest length
     Given a containing n An array of positive integers and a positive integer target .

Find the sum of the array ≥ target The smallest length of Continuous subarray [numsl, numsl+1, …, numsr-1, numsr] , And return its length . If there is no sub array that meets the conditions , return 0 .

2 Title Example

Example 1：

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

Example 2：

Input ：target = 4, nums = [1,4,4]
Output ：1

Example 3：

Input ：target = 11, nums = [1,1,1,1,1,1,1,1]
Output ：0

3 Topic tips

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

4 Ideas

The sliding window
So called sliding window , It's constantly adjusting the starting and ending positions of subsequences , So we can get the result that we want to think about .

First of all, think about If you use one for loop , Then it should mean The starting position of the sliding window , Or end position .

If only one for Loop to express The starting position of the sliding window , So how to traverse the remaining termination positions ？

The key to solving the problem is How the start of the window moves
The beauty of sliding windows is based on the current subsequence and size , Constantly adjust the starting position of subsequences . So that O(n^2) The violent solution is reduced to O(n)
therefore , The index of this loop , It must mean The end position of the sliding window .

5 My answer

class Solution {
    

    //  The sliding window 
    public int minSubArrayLen(int s, int[] nums) {
    
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
    
            sum += nums[right];
            while (sum >= s) {
    
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}