leetcode 209. Minimum length subarray

leetcode 209. Subarray with the smallest length

Hello everyone , I'm studying konjak in grade five of primary school , Focus on the back end , Witness the growth of konjaku together , Your comments, praise and attention are my biggest motivation , If you have any mistakes, please let me know , Thank you very much . Let's support originality ！ There is a mistake in writing .

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 [numsl, numsl+1, …, numsr-1, numsr] , And return its length . If there is no sub array that meets the conditions , return 0 .

Answer 1

Use for Circular violence

Traverse the array from the first element of the array , Add the values of each element , If the element is greater than or equal to the given value, the added array length will be compared with the original length, and the value will be updated according to the smaller length , After traversal, judge whether it is the same as the initial value , If it is different, the updated value will be returned , Otherwise return to 0

class Solution {
    
public:
    int minSubArrayLen(int target, vector<int>& nums) {
    
        int result=__INT32_MAX__;
        int arrLength=0;
        int sum;
        for(int i=0;i<nums.size();i++){
    
            sum=0;
            for(int j=i;j<nums.size();j++){
    
                sum+=nums[j];
                if(sum>=target){
    
                    arrLength=j-i+1;
                    result=arrLength>result?result:arrLength;
                    break;
                }
            }
        }
        return result==__INT32_MAX__?0:result;
    }
};

Explanation 2

Using the slide window

Add the data from the first element , If the data is greater than or less than the given value , Start decrementing elements from scratch , Then continuously update the length of the qualified array , Finally, judge whether the length is the same as the initial value , Different, return the updated value , Otherwise return to 0

class Solution {
    
public:
    int minSubArrayLen(int target, vector<int>& nums) {
    
        int result=__INT32_MAX__;
        int arrLength=0;
        int sum=0;
        int j=0;
        for(int i=0;i<nums.size();i++){
    
           sum+=nums[i];
           while (sum>=target)
           {
    
               arrLength=i-j+1;
               result=arrLength<result?arrLength:result;
               sum-=nums[j++];
               /* code */
           }
           
        }
        return result==__INT32_MAX__?0:result;
    }
};