209.Small length array

topic：

Given n The array of a positive integer and a positive integer target 。

Find out the array to satisfy it ≥ target The smalle Continuous array [numsl, numsl+1, ..., numsr-1, numsr] ，And return its length。If there is no conditional sub -array，return 0 。

 

Exemplary example 1：

enter：target = 7, nums = [2,3,1,2,4,3]
Output：2
explain：Sub -array [4,3] 是该条件下的Small length array。

Exemplary example 2：

enter：target = 4, nums = [1,4,4]
Output：1

Exemplary example 3：

enter：target = 11, nums = [1,1,1,1,1,1,1,1]
Output：0

 

hint：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

 

Advance：

• If you have achieved it O(n) Time complexity solution, Please try to design a O(n log(n)) Time complexity solution。

Related Topics

Array

Two -point search

Prefix and

Sliding window

👍 1652

👎 0

[209.Small length array.md]()

Thought：

Originally planned to use double pointers，But my double pointer is over time。

Code：

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n+1   # inf
        s = 0
        left = 0
        for right, x in enumerate(nums):
            # Record the results of the previous additional addition
            s += x
            # Move the left point,left <= right,Because of this and the front of this numbersalready>=targetOver，SosReduce the number of digital judgments can still be reduced
            while s - nums[left] >= target:
                s -= nums[left]
                left += 1
            if s >= target:
                ans = min(ans, right-left+1)
        return ans if ans <= n else 0