写在前面：给自己定一个小目标，每周写一个程序员必须知道的算法题（大厂面试频率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 道题的时候，一共有十几万人上来做题，但全部做完的只有十几个，万分之一。所以，只要你能坚持，就可以超过这个世界上绝大多数人。当然，坚持也不是要苦苦地坚持，你要把坚持变成一种习惯，就像吃饭喝水一样，你感觉不到太多的成本付出。只有这样，你才能够真正坚持。 ---陈皓
希望我的这些话可以让你有足够的动力坚持下去，欢迎大家关注我，和我一起坚持学习【每周算法】，直到将坚持养成习惯。另外有问题大家评论区讨论，积极沟通。如果本文对你有帮助，不要忘记点赞或收藏，拒绝伸手党！
网友评论