Leetcode-209-Size Subarray Sum

Posted 2022-07-12

10~13 min read

Minimum Size Subarray Sum

leetcode: https://leetcode.com/problems/minimum-size-subarray-sum/

Description:

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Idea:

solution1: Brute Force(Time exceed)

Step1: set a variable to record the length of elements that meet the requirement

Step2: traverse the nums and sum the elements until the sum larger than the target and compare the length of these element with current length, make the result point to the min one.

Step3:if the variable equal to the initial value,it means no substring meet the requirement, return 0; otherwise return the length.

Code:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        for(int i=0; i<nums.length; i++){
            int sum =0;
            for(int j=i; j<nums.length; j++){
                sum += nums[j];
                if(sum>=target){
                    result = Math.min(result,(j-i+1));
                }
            }
        }
        return result == Integer.MAX_VALUE ? 0:result;
    }
}

solution 2: Sliding Window

(1) Idea: change the start and end index of the subsequence dynamic to get the result that meet the requirement(it’s the process that continous searching the range)

(2) Key Points: set the content of the window; how to set and move the start and end index;

(3) Just use one loop, and use the index of the loop as the end index of the sliding window.

209.长度最小的子数组

In this Problem:

Step1: the content of the window is the subarray that meet sum >=target

Step2: when the meet the requirement, move the left bound index to next element to Narrow the scope

Step3: the index in the loop as fast index, it will control the right bound of the window, and move itself with the loop.

Code:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // set the variable to record the length
        int result = Integer.MAX_VALUE;
        // set the sum and slowindex to control the move the left bound of the range
        int sum = 0;
        int slowindex = 0;

        // traverse the nums and make the index as the right bound of the array
        for(int i=0; i<nums.length; i++){
            sum += nums[i];
            // compare the sum and target
            while(sum>=target){
                // get the current length of these elements meet the requirement and compare it with the length the result stored
                result = Math.min(result,(i-slowindex+1));
                // remove the left bound by self incresing, and get the sum of new range, if it also meet the requirement, check the length again, other wise change the right bound index to get the new range.
                sum -= nums[slowindex++];
            }
        }
        // check is there no subarray meet the requirement
        return result == Integer.MAX_VALUE ? 0:result;
    }
}

//Integer. MAX_VALUE represents the maximum positive integer value that can be represented in 32 bits (i.e., 2147483647 ).
//so that ensure if the sub array exists, it's length less than Integer. MAX_VALUE

Leetcode

Leetcode Array