【每周算法】长度最小的子数组

写在前面：给自己定一个小目标，每周写一个程序员必须知道的算法题（大厂面试频率Top100），把这个养成和洗脸睡觉一样的周长习惯，每一个经典题目咬烂嚼碎，解题思路和源代码都会贴出来，有想学算法的可以跟上我的脚步，Follow me~

题目描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
难度：mid
示例

输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶
如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(nlogn) 时间复杂度的解法

题解

双指针法

时间复杂度O(n), 空间复杂度O(1)
定义两个指针 left 和 right 分别表示子数组的开始位置和结束位置，初始状态下，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)
这里需要额外创建一个数组 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 中有现成的库 bisect 为我们实现了二分查找，但有时面试官可能会想让我们自己实现这个函数，这里我也贴出二分查找的实现代码，供大家参考。

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种解题方法，个人最推荐双指针法，虽然前缀和 + 二分查找法满足进阶要求，但可以看到，提高时间复杂度必然是要牺牲空间复杂度的，鱼和熊掌不可兼得，当应用到实际业务中，要根据时间更宝贵还是资源更重要来选择，所以没有哪一个更好，最好都能记住。如果实在记不住建议重点记忆双指针法，因为双指针法相对前缀和 + 二分查找法更好理解，而理解是记忆的基础，且双指针法已经是满足题目对时间复杂度的要求。

解题万能方法：

其实算法是有方法的，当有时间复杂度要求的时候，肯定不能用暴力法（即多层for循环遍历的情况），你往往需要考虑用一层循环来解决问题，而时间复杂度要求为O(logn)或O(nlogn)时，就要考虑如何通过空间换时间，这时候空间复杂度上往往会从O(1)变为O(n)，如本题的前缀和 + 二分查找法利用了前缀和sums数组，这就给你提供了一些解题思路，找到大体解决方向。

除了上面的解题技巧，第二个我要分享给大家的就是学习金字塔原理，学习不是光靠努力追求阅读、试听的速度和数量，这会让人产生低层次的勤奋和成长的感觉，这只是在使蛮力。要思考，要实践，要总结和归纳，否则，你只是在机械地重复某件事，而不会有质的成长的。

当年 LeetCode 只有 151 道题的时候，一共有十几万人上来做题，但全部做完的只有十几个，万分之一。所以，只要你能坚持，就可以超过这个世界上绝大多数人。当然，坚持也不是要苦苦地坚持，你要把坚持变成一种习惯，就像吃饭喝水一样，你感觉不到太多的成本付出。只有这样，你才能够真正坚持。 ---陈皓

希望我的这些话可以让你有足够的动力坚持下去，欢迎大家关注我，和我一起坚持学习【每周算法】，直到将坚持养成习惯。另外有问题大家评论区讨论，积极沟通。如果本文对你有帮助，不要忘记点赞或收藏，拒绝伸手党！