209. 长度最小的子数组

leetcode-209. 长度最小的子数组

如果使用暴力解法，需要用两个for循环嵌套，时间复杂度很明显是O(n^2)。

巧妙的方法是使用滑动窗口的方法，类似计算机网络中的内容，窗口由一前一后两个指针约束。窗口的前指针在循环中不停地前进，寻找最优解。当窗口中的内容不符合最优解的时候，移动后指针直到重新符合条件，再进入循环。

这样做的好处是，通过操作两个指针，只进行了一次循环，时间复杂度降低为O(n).

//经验不足导致的代码又臭又长
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = nums[0], fastIndex = 0, slowIndex = 0, length = 1, minLength = nums.size() + 1;
        if(sum >= target)
        {
            return 1;
        }
        while(fastIndex < nums.size() - 1)
        {
        fastIndex++;
        length++;
        sum += nums[fastIndex];
        while(sum - nums[slowIndex] >= target)
        {
            sum -= nums[slowIndex];
            slowIndex++;
            length --;
        }
        if(sum >= target)
        minLength = (length < minLength)? length : minLength;
        }
        if(minLength == nums.size() + 1)
        {
            return 0;
        }
        return minLength;  
    }
};