209. Minimum Size Subarray Sum

發表於 更新於 分類於 ， 閱讀次數： Disqus： 文章字數： 247

種類 : list
難度 : medium
題目 : 209.Minimum Size Subarray Sum

思維邏輯

  1. 使用sliding window(仍是two point)控制起始位置與終點位置
  2. 加總window內的集合
  3. 若sum(window) >= target, 更新起始位置與集合長度

解法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minSubArrayLen(nums: list, target: int) -> int:
    left, right, cur_sum = 0, 0, 0
    min_len = float('inf')              # 設最小範圍為無限大(無解)
    while right < len(nums):
        cur_sum += nums[right]
        while cur_sum >= target:        # 不能使用if原因: 已滿足條件(大於target)，必須在此刻縮小範圍
            min_len = min(min_len, right - left + 1)
            cur_sum -= nums[left]
            left += 1
        right += 1
    return min_len if min_len != float('inf') else 0    # 若為'無限大'代表無解

時間複雜度: 2n = O(n)

難點

  1. 外層loop並不是控制起始位置(若是的話與暴力解法相同)，而是控制終點位置
  2. 當cur_sum >= target時，是使用while而不是if
  3. while cur_sum >= target:內層迴圈控制起點

最佳解法

此為最佳解法
暴力解法時間複雜度: O(n^2)