current position:Home>"Double pointer" leetcode 209. Minimum length subarray (medium)

"Double pointer" leetcode 209. Minimum length subarray (medium)

2021-08-27 08:53:31 _ Monday

One 、 Understand the topic

Attach a link to the original title :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 Continuous subarray with the smallest length of [numsl, numsl+1, ..., numsr-1, numsr] , And return its length . If there is no sub array that meets the conditions , return 0 .

Example :

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

Two 、 Problem analysis

According to the meaning of the above question , Let's take a look at the specific Their thinking :

  • Define two pointers l and r , Point to the array with the subscript 0 The location of . Move only one pointer at a time , Step by step to 1 ;
  • l The pointer doesn't understand , r Pointer backward . until sum >= target , Record the minimum window length at this time min ;
  • l Pointer backward , r The pointer doesn't move . Judge sum Greater than or equal to target , If yes, reduce the minimum window length min , Otherwise repeat the steps 2;
  • min The value cannot exceed the maximum integer limit .

3、 ... and 、 Code implementation

According to the above question , We will use js To achieve 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 the left pointer , Point to the head of the array 
    let l = 0;
    // 2. Minimum window length for storage , Initialization length is array length  + 1
    let min = len + 1;
    // 3. The sum of the array 
    let sum = 0;
    // 4. Define the right pointer , Let the right pointer traverse the entire array 
    for(let r = 0; r < len; r++){
        // 4.1  Keep moving the right pointer to the right , And add it to the previous number 
        sum += nums[r];
        // 4.2  When you meet sum Greater than or equal to the target value 
        while(sum >= target){
            // 4.2.1  Reduce a window value 
            sum -= nums[l];
            // 4.2.2  Determine the size of the sliding window and the smallest sliding window 
            min = Math.min(r - l + 1, min);
            // 4.2.3  Move the left pointer one bit to the right 
            l++;
        }
    }
    // 5. Determine whether the minimum value exceeds the actual array length , If it exceeds, there is no qualified array , return 0; Otherwise, the minimum value is returned min value 
    return min === len + 1 ? 0 : min;
}
​
console.log(minSubArrayLen(7,[2,3,1,2,4,3])); // 2
 Copy code 

That's about Subarray with the smallest length The antithesis of , I don't know if it will help my friends ?

See you next time

copyright notice
author[_ Monday],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2021/08/20210827085327275b.html

Random recommended