每日算法之LeetCode 209： Minimum Size

LeetCode 209： Minimum Size Subarray Sum（长度最小的子数组）

Q:Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

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

看到这个题目，需要和面试官交流的问题:

1.什么是子数组。因为子数组的在不同的题目定义是不一样的，有的不一定要求是连续的元素。

2.关于一些特殊解。比如没有解返回什么，这里题目已明确说明了如果没有满足sum>=s的就返回0

如果有多个解是返回哪一组？这里因为返回的是长度，所以只会有一个答案。如果返回的是一个子数组，就需要考虑这个问题。

当然，第一时间想到的肯定就是暴力解法了，差一点的时间复杂度O(n^{3)，优化一下最好可以达到O(n}2)。肯定都不是我们满足的了。

那么有什么比较厉害的解法呢？

这里要说一个词叫做“滑动窗口”，和之前说的“指针碰撞”有一点像。只不过这是两个指针组成的一块像窗口一样的区域。只需要通过不断移动这个窗口就可以解决这个问题了。

下图的红色区域就是上面所说的窗口。

minsubarray.png

关键在于怎么移动这个窗口解决此题呢

（1）首先区间[i,j]的定义很重要
要保证最开始的时候窗口不包含元素，很简单，只需要将j=-1就好了

 int i=0; int j=-1;

（2）初始化的长度为数组的长度+1。因为要保证在有符合条件的子数组情况下，这个值初始值最好是最大值也就是数组的长度加1

（3）最后就是移动窗口了。
首先要保证窗口不越界，

然后如果子数组小于目标和，右指针j右移，使窗口变大

如果子数组大于目标和，左指针j右移，使窗口变小

之后判断如果子数组元素和大于目标和并且此时符合子数组的长度变小了，则取这个较小的子长度

（4）需要注意的是数组如果为空，或者没有找到符合条件的子数组，那么就返回0。也即我的子数组长度len和初始值一样没有改变，返回0.

此处需要上一波完整代码了

int minSubArrayLen(int s, vector<int>& nums) {
        int i=0; int j=-1; //保证开始的时候窗口不包含元素
        int sum=0;
        int len=nums.size()+1;  //初始化的长度为数组的长度，假设存在子数组元素和大于目标和，那么这个值肯定是最大值

        while(i<nums.size()){
          
            if(sum<s&&j+1<nums.size()) sum+=nums[++j];   //如果子数组小于目标和，右指针右移，使窗口变大
            else sum-=nums[i++];                         //如果子数组大于目标和，左指针右移，使窗口变小

            if(sum>=s&&len>j-i+1) len=j-i+1;              //如果子数组元素和大于目标和并且此时符合子数组的长度变小了，则取这个较小的子长度
        }
        if(len==nums.size()+1)  return 0;
        return len;
    }

测试一下效率，结果还是很帅的，看下图【滑稽笑】：

image.png