# LeetCode Medium 209. Minimum Size Subarray Sum

tags: leetcode

問題

• Explore
• Problems

アイデア

｢n個の正の整数の配列を与えられた時，s以上の和を持つ連続した部分列の最小の大きさを探せ｣という問題です．ただし，部分列の大きさは最低でも2で，大きさが1のときは0を返します．

全探索をしようとすると計算量のオーダーが$O(N²)$になってしまいます．これだと時間を掛けすぎなので計算量を改善する方法を探します．

ここで，連続した部分列の話をしているので，左端と右端に注目すれば$O(N)$で問題が解けそうだと考えることができます．

解法

• 右端を和に足していき，和がs以上になったとき，答えの部分列の長さを更新します．
• そして，左端を取り除き，長さも短くします．

計算量

配列の要素の数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(1)$

Python

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        min_len = float('inf')
        left, cur_sum = 0, 0
        for right in range(len(nums)):
            cur_sum += nums[right]
            while cur_sum >= s:
                min_len = min(min_len, right - left + 1)
                cur_sum -= nums[left]
                left += 1
        return min_len if min_len != float('inf') else 0