Leetcode-209-subarray with the smallest length

Subarray with the smallest length

Title Description ： 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 [nums _l, nums_l+1​​, …, nums_r-1, nums_r] , And return its length . If there is no sub array that meets the conditions , return 0 .

Please refer to LeetCode Official website .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/minimum-size-subarray-sum/
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Solution 1 ： The sliding window

First , Judge special cases , If the array is empty , Go straight back to 0.

otherwise , Use the sliding window method to judge whether there is the smallest continuous subarray , The specific processing logic is as follows ：

• First , Declare the left and right boundaries of the sliding window , And use minLen Record the length of the smallest continuous subarray ;
• Traversal array , Until the right boundary traverses to the last digit position of the original array ;
• Calculates the sum of successive subarrays of the current range , Judge whether the current sum is better than target Small , If not less than , Move the left boundary of the window to the right , And judge whether the current continuous length is the smallest ; If it is less than , Move the right boundary of the window to the right .

Last , Judge minLen Have you found , Returns if it does not exist 0; otherwise , return minLen.

public class LeetCode_209 {
    
    /** *  The sliding window  * * @param target  The target  * @param nums  Original array  * @return */
    public static int minSubArrayLen(int target, int[] nums) {
    
        //  If the array is empty , Go straight back to 0
        if (nums == null || nums.length == 0) {
    
            return 0;
        }
        //  Record the length of the smallest continuous subarray 
        int minLen = Integer.MAX_VALUE;
        //  Slide the left and right boundaries of the window 
        int left = 0, right = 0;
        //  Traverse until the right boundary traverses to the last digit position of the original array 
        while (right < nums.length) {
    
            int sum = 0;
            //  Calculates the sum of successive subarrays of the current range 
            for (int i = left; i <= right; i++) {
    
                sum += nums[i];
            }
            //  Judge whether the current sum is better than target Small , If not less than , Move the left boundary of the window to the right , And judge whether the current continuous length is the smallest ; If it is less than , Move the right boundary of the window to the right 
            if (sum >= target) {
    
                minLen = Math.min(minLen, right - left + 1);
                left++;
            } else {
    
                right++;
            }
        }

        if (minLen == Integer.MAX_VALUE) {
    
            return 0;
        }
        return minLen;
    }

    public static void main(String[] args) {
    
        //  Test case one , Expected output ： 2
        System.out.println(minSubArrayLen(7, new int[]{
    2, 3, 1, 2, 4, 3}));
        //  Test case 2 , Expected output ： 0
        System.out.println(minSubArrayLen(11, new int[]{
    1, 1, 1, 1, 1, 1, 1, 1}));
    }
}

【 Daily message 】 Life is like climbing a mountain , And looking for the mountain to find the way , But it's a learning process , In the process , Study firmly 、 calm , Learn how to find life from panic .