LeetCode - #209 長度最小的子數組

​

前言

我們社群陸續會将顧毅（Netflix 增長黑客，《iOS 面試之道》作者，ACE 職業健身教練。）的 Swift 算法題題解整理為文字版以友善大家學習與閱讀。

LeetCode 算法到目前我們已經更新到 208 期，我們會保持更新時間和進度（周一、周三、周五早上 9:00 釋出），每期的内容不多，我們希望大家可以在上班路上閱讀，長久積累會有很大提升。

不積跬步，無以至千裡；不積小流，無以成江海，Swift社群 伴你前行。如果大家有建議和意見歡迎在文末留言，我們會盡力滿足大家的需求。

難度水準：中等

1. 描述

給定一個含有 ​

​n​

​​ 個正整數的數組和一個正整數 ​

​target​

​ 。

找出該數組中滿足其和 ​

​≥ target​

​ 的長度最小的 連續子數組 ​

​[numsl, numsl+1, ..., numsr-1, numsr]​

​​ ，并傳回其長度。如果不存在符合條件的子數組，傳回 ​

​0​

​ 。

2. 示例

示例 1

輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數組 [4,3]      

示例 2

輸入：target = 4, nums = [1,4,4]
輸出：1      

示例 3

輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0      

提示：

• ​

  ​1 <= target <= 10^9​

  ​
• ​

  ​1 <= nums.length <= 10^5​

  ​
• ​

  ​1 <= nums[i] <= 10^5​

  ​

進階：

• 如果你已經實作​

  ​O(n)​

  ​​ 時間複雜度的解法, 請嘗試設計一個​

  ​O(n log(n))​

  ​ 時間複雜度的解法。

3. 答案

class MinimumSizeSubarraySum {
    func minSubArrayLen(_ s: Int, _ nums: [Int]) -> Int {
        var miniSize = Int.max, start = 0, currentSum = 0

        for (i, num) in nums.enumerated() {
            currentSum += num

            while currentSum >= s, start <= i {
                miniSize = min(miniSize, i - start + 1)

                currentSum -= nums[start]
                start += 1
            }
        }

        return miniSize == Int.max ? 0      

• 主要思想：兩個指針，錨定前者，并向前移動後者，以確定子數組的和剛好覆寫目标。
• 時間複雜度：O(n)
• 空間複雜度：O(1)

關于我們