209.md

[209] Minimum Size Subarray Sum

Description

link

---

General

• 1248 Count Number of Nice Subarrays
• 1234 Replace the Substring for Balanced String
• 1004 Max Consecutive Ones III
• 930 Binary Subarrays With Sum
• 992 Subarrays with K Different Integers
• 904 Fruit Into Baskets
• 862 Shortest Subarray with Sum at Least K
• 209 Minimum Size Subarray Sum

---

Solution 1 不存在负数

• 如果不存在负数，直接使用最简单的滑动窗口即可得到答案
• 如果要nlogn复杂度的解，则求sum的数组后再进行binary search

---

Code 1

O(nlogn)

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        result = len(nums) + 1
        for idx, n in enumerate(nums[1:], 1):
            nums[idx] = nums[idx - 1] + n
        left = 0
        for right, n in enumerate(nums):
            if n >= s:
                left = self.find_left(left, right, nums, s, n)
                result = min(result, right - left + 1)
        return result if result <= len(nums) else 0

    def find_left(self, left, right, nums, s, n):
        while left < right:
            mid = (left + right) // 2
            if n - nums[mid] >= s:
                left = mid + 1
            else:
                right = mid
        return left

---

Solution 2 存在负数

• 862 Shortest Subarray with Sum at Least K

1. 思路是每次再一个sum节点，往后寻找到for B[i], find the smallest j that B[j] - B[i] >= K
2. d保存的是【index, num】并且是按照index的顺序，同时必须要保证d的num顺序是升序状态
3. 为什么要保证升序状态，因为如果我们知道B[i] <= B[d.back()]同时i > d.back，那么对于后面的每次计算，B[i]都会比d.back来的要短，所以不需要保留

---

Code 2

O(n)

class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:
        d = collections.deque([[0, 0]])
        res, cur = float('inf'), 0
        for i, a in enumerate(A):
            cur += a
            while d and cur - d[0][1] >= K:
                res = min(res, i + 1 - d.popleft()[0])
            while d and cur <= d[-1][1]:
                d.pop()
            d.append([i + 1, cur])
        return res if res < float('inf') else -1