Location>code7788 >text

The subarray with the smallest length

Popularity：771 ℃/2024-08-14 17:46:11

**Question**

Given an array of n positive integers and a positive integer target. Find the number of integers in the array that satisfy the sumgreater than or equal to target The length of the smallestsubarray [numsl, numsl+1, ... , numsr-1, numsr] and returns its length. If no subarray exists that matches the condition, 0 is returned.

 

**Note**

Definition of a subarray: an orprogressionElements in multiple arrays form a subarray (subarrays contain at least one element), note this continuity.

 

**Solution**

The solution can be divided into two types, the first is the violent cracking method, which is also the most intuitive method, and the second is the sliding window method

 

**Brute force method**

 

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # Initial Set min_value to infinity
        min_value=float('inf')
        flag=0

        input_len=len(nums)

        for i in range(input_len):
            tmp_value=0
            for j in range(i,input_len):
                # Nested traversal, because you're looking for subarrays, continuity.
                tmp_value+=nums[j]
                # If it is greater than target, compare it to min_value and choose the smallest
                if tmp_value>=target:
                    min_value=min(min_value,j-i+1)
                    flag=1
                    # If the value is greater than the target, the loop ends.
                    break
        
        if flag:
            return min_value
        else:
            return 0

But the time complexity of the above solution is in the N-square, how to optimize this violent solving method, we use a sliding window, change the right pointer, if the current cumulative value is greater than the target value, then move the left pointer to find the smallest subarray, the code is as follows:

 

**Sliding window method**

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # Initial Set min_value to infinity
        min_value=float('inf')
        left=0

        num_len=len(nums)
        tmp_value=0
        # Go all the way to the right.
        for j in range(num_len):

            tmp_value+=nums[j]

            while tmp_value>=target:

                min_value=min(min_value,j-left+1)
                # Slide to the left to find the smallest subarray
                tmp_value-=nums[left]
                left+=1

        return min_value if min_value!=float('inf') else 0

 

<Previous Next>