Leetcode 209: Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

对于 subarray 的题目，sliding window， dp 可以解，sliding window的局限性在于，固定窗口左边移动右边sum是在增大的， 固定窗口右边移动左边sum是在减小的，这种情况下对于array里面的元素不一致，有positive 也有 negative的情况，sliding window是不适用的，因为固定窗口任何一边，移动一边sum都是可能增大或者减小的，依据移出的数的正负而定，所以此时窗口移动就很难获取所有可能的sum了，也不能确定窗口怎么移。 这个题目，array里面都是positive integers, 所以sliding window的方法能够找到所有可能的sum>=target的subarray，只要每次更新minimal length就好了。采用：sliding window 2. 固定右边，移左边直至condition 不成立为止，再考虑移动右边（跟之前课上讲的longest subarray without duplicate chars &&  minimal subarray with anal of word 解法类似）。 （sliding window 1:  固定左边，移动右边，窗口的大小固定，右边移出固定大小的时候如果满足condition，左边移动一步，右边继续往后移，如果不满足conditin，左边移动到右边，右边继续往后移，就相当于固定窗口大小，看窗口内的元素是否满足。之前讲过match word, match chars）

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        //sanity check
        if (nums.size() == 0) return 0;
        int slow = 0;
        int fast = 0;
        int minl = INT_MAX;
        int sum = 0;
        bool flag = false;
        for (; fast < nums.size(); fast++) {
            sum += nums[fast];
            while (sum >= s) {
                flag = true;
                minl = min(minl, fast - slow +1);
                sum -= nums[slow];
                slow++;
            }
        }
        return flag ? minl : 0;
    }
};

相关的题目： longest subarray with even number of 0s, and 1s

题目题: 看起来跟上一题类似，当把0s都变成-1时，转化为sum = 0最长子串， 但是由于这样转换之后array里面存在正数和负数，所以不能用sliding window来做，
1： M[i]: 0-i sum
2. hash_table : key sum: value : index.