leetcode长度最小的子数组

欢迎关注本人的微信公众号AI_Engine

国庆归来，依旧精彩。leetcode系列第4篇~

题目：

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

示例: 

输入:s = 7, nums = [2,3,1,2,4,3]

输出:2

解释:子数组[4,3]是该条件下的长度最小的连续子数组。

答案：

分析：这道题同样是关于数组与子数组问题的考察，在近两年内出现过该面试题的公司有：今日头条，腾讯，苹果，facebook，阿里巴巴，华为。同之前的一道题目类似，也需要计算数组的前缀，不同的是这道题比较优秀的解法是利用双指针（也成对撞指针）会更便于理解。有的同学或许听到指针就蒙圈了，然后还要对撞，可能直接就放弃阅读了。千万不要~其实这两个指针就完全可以理解成一对flag，然后这两个flag之间的区域就是我们的目标窗口，就好似曾经的相机底片一样，我们理解的越简单越好。首先我们还是对题目降维，题目要求我们求出满足条件的长度最小子数组，我们先不搭理他，我们想如何求出满足条件的子数组就好。想到子数组就应该想到区域，想到区域就会想到边界，想到边界就会想到flag。那么我们首先定义左侧边界（指针） left ，而且现在我们只考虑左侧边界的索引值为0的情况，然后利用右侧边界right对数组进行遍历，并计算前缀和。当计算出的前缀和一旦大于等于目标值s时，此时的区域就是满足条件的子数组。我们就将初始化的最短长度与当前的长度进行比较与更新（这里初始化的最短长度我设定为数组的长度，因为我之间进行了异常判断。当然，也可以设定为无穷大）。现在我们对题目进行升维：假设当前我们已经找到了某个区域完全满足上述条件，那么现在这个区域内的子数组中是否还存在更短的子数组也满足条件（极限条件下，当right遍历的到一个超大值时，也许单凭这个超大值num[right]就完全满足大于等于s的条件，此时的最短长度就为1了），所以为了寻求当前区域内中满足条件的的子数组，我们逐渐逼近right，即右移left，注意：在右移left之前，pre_sum应先减去当前的num[left]，然后再进行left右移（left += 1）。现在窗口变小了，但是限定条件不变：pre_sum >= s。也就是说只要满足这个条件，窗口就可以进行减小，left就可以右移，然后更新min_len。当不满足pre_sum >= s这个条件时，我们就将right进行右移，即对原始数组进行遍历，然后重复上述过程就可以求得满足条件的最短子数组了。大致的流程如下：

1 .滑动窗口右端 R 开始移动，直到区间满足给定的条件，也就是和大于 7 ，此时停止于第三个元素 2，当前的最优长度为 4

2. 滑动窗口左端 L 开始移动，缩小滑动窗口的大小，停止于第一个元素 3，此时区间和为 6，使得区间和不满足给定的条件（此时不大于 7）

3. 滑动窗口右端 R 继续移动，停止于第四个元素 4，此时和位 10 ，但最优长度仍然为 4

。。。。。。

按照惯例来看下结果吧：