专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
有的人一找不到工作就自怨自艾，怨天尤人，一度怀疑自己，甚至破罐破摔，自甘堕落，有的甚至为此感到焦虑，导致最后发展成了抑郁症。实际上找不到工作并不都是你的错，而是人家已经招满了，还在继续招主要是给公司做宣传，所以这个时候你怎么可能过，就算是爱因斯坦来了一样收不到offer。下面一位网友透露出了校招的实情，原来都是套路。
网友评论：
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第209题：长度最小的子数组。
问题描述
来源：LeetCode第209题
难度：中等
给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例1：
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例2：
输入：target = 4, nums = [1,4,4] 输出：1
1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
问题分析
这题是让找出长度最小的连续子数组，并且这个子数组中所有元素的和大于等于target，这是一道典型的滑动窗口问题。
窗口滑动的时候只需要累加窗口内的值sum，然后判断sum是否大于等于target，或者用target减去窗口内所有元素的值，然后判断target是否小于等于0，这两种方式都可以，我们使用第二种方式来看下，解决方式如下：
使用两个指针left和right分别指向窗口的左右边界，滑动窗口右边界的时候就用target减去右边界的值，如果target小于等于0，说明窗口是满足条件的，但不一定是最小的，所以还需要通过滑动窗口的左边界来查找最小值。
关于滑动窗口的使用模板和几种滑动窗口的总结在我的书中第8章也都有详细的描述，这里就不在重复介绍，我们来看下这题的代码。
JAVA：
public int minSubArrayLen(int target, int[] nums) {
int left = 0, right = 0;// 窗口的左右边界
int min = Integer.MAX_VALUE;// 满足条件的最小窗口长度
while (right < nums.length) {
target -= nums[right++];// 滑动窗口右边界
// 如果窗口满足条件就缩小窗口，移除窗口左边界元素，直到窗口
// 不满足条件为止，顺便记录下满足条件的窗口最小长度。
while (target <= 0) {
min = Math.min(min, right - left);
target += nums[left++];// 移除左边界
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}C++：
public:
int minSubArrayLen(int target, vector
&nums) { int left = 0, right = 0;// 窗口的左右边界 int minLen = INT_MAX;// 满足条件的最小窗口长度 while (right < nums.size()) { target -= nums[right++];// 滑动窗口右边界 // 如果窗口满足条件就缩小窗口，移除窗口左边界元素，直到窗口 // 不满足条件为止，顺便记录下满足条件的窗口最小长度。 while (target <= 0) { minLen = min(minLen, right - left); target += nums[left++];// 移除左边界 } } return minLen == INT_MAX ? 0 : minLen; }
Python：
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left, right = 0, 0 # 窗口的左右边界
minLen = 2 ** 31 # 满足条件的最小窗口长度
while right < len(nums):
target -= nums[right] # 滑动窗口右边界
right += 1
# 如果窗口满足条件就缩小窗口，移除窗口左边界元素，直到窗口
# 不满足条件为止，顺便记录下满足条件的窗口最小长度。
while target <= 0:
minLen = min(minLen, right - left)
target += nums[left] # 移除左边界
left += 1
return 0 if minLen == 2 ** 31 else minLen笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴