寫在前面：給自己定一個小目標熔萧，每周寫一個程序員必須知道的算法題（大廠面試頻率Top100）谒拴，把這個養(yǎng)成和洗臉睡覺一樣的周長習慣，每一個經典題目咬爛嚼碎哑子，解題思路和源代碼都會貼出來跪妥，有想學算法的可以跟上我的腳步鞋喇，F(xiàn)ollow me~

題目描述

給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和 ≥ s 的長度最小的連續(xù)子數組眉撵，并返回其長度侦香。如果不存在符合條件的連續(xù)子數組，返回 0纽疟。
難度：mid
示例

輸入：s = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數組 [4,3] 是該條件下的長度最小的連續(xù)子數組罐韩。

進階
如果你已經完成了 O(n) 時間復雜度的解法, 請嘗試 O(nlogn) 時間復雜度的解法

題解

雙指針法

時間復雜度O(n), 空間復雜度O(1)
定義兩個指針 left 和 right 分別表示子數組的開始位置和結束位置，初始狀態(tài)下污朽，left 和 right 都指向下標 0散吵，子數組 cur_sum = 0。
每一輪迭代蟆肆，如果子數組 cur_sum ≥ s矾睦，則更新子數組的最小長度，然后將 cur_sum 中減去 nums[left]v并將 left 右移颓芭，直到 cur_sum < s，在此過程中同樣更新子數組的最小長度柬赐。在每一輪迭代的最后亡问，right 右移。

import datetime
import bisect
from typing import List


class Solution:
    # 3. 雙指針法
    def min_sub_array_len_3(self, s, nums: List[int]) -> int:
        if not nums:
            return 0

        len_nums = len(nums)
        left, cur_sum = 0, 0
        min_len = len_nums + 1

        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 != len_nums + 1 else 0

前綴和 + 二分查找法

時間復雜度O(nlogn), 空間復雜度O(n)
這里需要額外創(chuàng)建一個數組 sums 用于存儲 nums 的前綴和，遍歷有序數組 sums州藕，需要找到 s + sums[i - 1] 的臨界值 bound 的位置并更新最小長度束世。

    # 4. 前綴和 + 二分查找法
    def min_sub_array_len_4(self, s: int, nums: List[int]) -> int:
        if not nums:
            return 0

        len_nums = len(nums)
        min_len = len_nums + 1
        sums = [0]

        for i in range(len_nums):
            sums.append(sums[-1] + nums[i])

        for i in range(1, len_nums + 1):
            target = s + sums[i - 1]
            # 二分查找法：返回target應該插在sums中的下標位置
            bound = bisect.bisect_left(sums, target)
            if bound != len(sums):
                min_len = min(min_len, bound - (i - 1))

        return min_len if min_len != len_nums + 1 else 0

因為這道題數組中每個元素都為正，所以前綴和一定是遞增的床玻，否則這里就不能使用二分查找法了毁涉。
雖然 Python 中有現(xiàn)成的庫 bisect 為我們實現(xiàn)了二分查找，但有時面試官可能會想讓我們自己實現(xiàn)這個函數锈死，這里我也貼出二分查找的實現(xiàn)代碼贫堰，供大家參考。

def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

實際上本題我嘗試用了4種方法待牵，法1法2為暴力法，時間復雜度為O(n^2)，解題思路比較好理解娶眷，但缺點也很明顯饰序，如果實在想不起上面兩種方法，最后推薦大家使用這兩種方法（千萬不能讓面試官覺得你連一種思路都沒有）贰拿。

暴力法

時間復雜度O(n^2) 空間復雜度O(1)
設最小長度為無窮大蛤袒，遍歷數組 nums，對于每個子數組的開始下標 i膨更，需要找到 j >= i妙真，使得 sum(nums[i:j]) >= s，并更新子數組的最小長度询一。

    # 1. 暴力法
    def min_sub_array_len_1(self, s: int, nums: List[int]) -> int:
        if not nums:
            return 0

        len_nums = len(nums)
        min_len = len_nums + 1

        for i in range(len_nums):
            cur_sum = 0
            for j in range(i, len_nums):
                cur_sum += nums[j]
                if cur_sum >= s:
                    min_len = min(min_len, j - i + 1)
                    break

        return min_len if min_len != len_nums + 1 else 0

時間復雜度O(n^2) 空間復雜度O(1)
設最小長度為 i+1隐孽，遍歷數組 nums，對于每個子數組的開始下標 j健蕊，需要找到 sum(nums[j:j + i + 1]) >= s菱阵，并返回子數組的最小長度 i+1。

    # 2.  暴力法
    def min_sub_array_len_2(self, s: int, nums: List[int]) -> int:
        if not nums:
            return 0

        len_nums = len(nums)

        for i in range(len_nums):
            for j in range(len_nums - i):
                if sum(nums[j:j + i + 1]) >= s:
                    return i + 1

總結

綜上4種解題方法缩功，個人最推薦雙指針法晴及，雖然前綴和 + 二分查找法滿足進階要求，但可以看到嫡锌，提高時間復雜度必然是要犧牲空間復雜度的虑稼，魚和熊掌不可兼得，當應用到實際業(yè)務中势木，要根據時間更寶貴還是資源更重要來選擇蛛倦，所以沒有哪一個更好，最好都能記住啦桌。如果實在記不住建議重點記憶雙指針法溯壶，因為雙指針法相對前綴和 + 二分查找法更好理解及皂，而理解是記憶的基礎，且雙指針法已經是滿足題目對時間復雜度的要求且改。

解題萬能方法：

其實算法是有方法的验烧，當有時間復雜度要求的時候，肯定不能用暴力法（即多層for循環(huán)遍歷的情況）又跛，你往往需要考慮用一層循環(huán)來解決問題碍拆，而時間復雜度要求為O(logn)或O(nlogn)時，就要考慮如何通過空間換時間慨蓝，這時候空間復雜度上往往會從O(1)變?yōu)?code>O(n)感混，如本題的前綴和 + 二分查找法利用了前綴和sums數組，這就給你提供了一些解題思路菌仁，找到大體解決方向浩习。

當年 LeetCode 只有 151 道題的時候，一共有十幾萬人上來做題地来，但全部做完的只有十幾個戳玫，萬分之一。所以未斑，只要你能堅持咕宿，就可以超過這個世界上絕大多數人。當然蜡秽，堅持也不是要苦苦地堅持府阀，你要把堅持變成一種習慣，就像吃飯喝水一樣芽突，你感覺不到太多的成本付出试浙。只有這樣，你才能夠真正堅持寞蚌。 ---陳皓

希望我的這些話可以讓你有足夠的動力堅持下去田巴，歡迎大家關注我力细，和我一起堅持學習【每周算法】，直到將堅持養(yǎng)成習慣固额。另外有問題大家評論區(qū)討論，積極溝通煞聪。如果本文對你有幫助斗躏，不要忘記點贊或收藏，拒絕伸手黨昔脯！