First, understand the topic

209. Smallest subarray size

Given an array of n positive integers and a positive integer target.

Find the smallest contiguous subarray [numsl, numSL +1,…, numsr-1, numsr] that satisfies the sum and ≥ target, and return its length. If no subarray exists, return 0.

Example:

Input: target = 7, nums = [2,3,1,2,4,3] output: 2 description: the subarray [4,3] is the smallest subarray in this condition.Copy the code

Ii. Solution analysis

According to the above description, let’s look at the specific solution of the problem:

  • Define two Pointersl 和 r, respectively pointing to arrays with subscripts0The location of the. Move only one pointer at a time, step is1 ；
  • lThe pointer doesn’t understand,rThe pointer moves back. untilsum >= targetRecord the minimum window length at this timemin ；
  • lThe needle moves back,rThe needle doesn’t move. judgesumWhether greater than or equal totargetIf yes, reduce the minimum window lengthminOtherwise, repeat Step 2.
  • minThe value cannot exceed the maximum integer limit.

Three, code implementation

Based on the above solution, we will use JS to implement this problem. The specific implementation code is as follows:

/ * * *@param {number} target
 * @param {number[]} nums
 * @return {number}* /
​
 let minSubArrayLen = function(target, nums){
    const len = nums.length;
    // 1. Define a left pointer to the head of the array
    let l = 0;
    // 2. Store the minimum window length. The initial length is array length + 1
    let min = len + 1;
    // 3. Store the sum of arrays
    let sum = 0;
    // 4. Define a right pointer that traverses the array
    for(let r = 0; r < len; r++){
        // 4.1 Keep moving the right pointer to the right and add it to the preceding number
        sum += nums[r];
        // 4.2 When sum is greater than or equal to the target value
        while(sum >= target){
            // 4.2.1 Shrink a window value
            sum -= nums[l];
            4.2.2 Determine whether the sliding window size is smaller than the minimum sliding window size
            min = Math.min(r - l + 1, min);
            // 4.2.3 Move the left pointer to the right one bitl++; }}// 5. Check whether the minimum value exceeds the actual array length. If the value exceeds the actual array length, there is no array that meets the condition. Otherwise, return the minimum min value
    return min === len + 1 ? 0 : min;
}
​
console.log(minSubArrayLen(7[2.3.1.2.4.3])); / / 2
Copy the code

The smallest subarray size is the smallest subarray size.

We’ll see you next time at 👋👋👋