LeetCode 209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
 

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
 

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

分析：

　　涉及到连续子数组的问题，可以优先考虑使用 滑动窗口法 求解。

　　此问题中，定义快慢两个指针，快指针右移，记录快慢指针范围内元素的和，一旦满足条件，记录子数组长度，并且保持快指针不变，慢指针右移，仍然比较两指针范围内元素之和，满足条件，则判断子数组长度是否比前一次满足条件的子数组长度小，更新最小子数组长度。

　　开始定义了滑动窗口长度为INT_MAX（系统默认的一个很大的值），若滑动窗口长度没有发生变化，返回-1，表示没找到符合条件的滑动窗口，否则，返回滑动窗口的长度。

动图如下（https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html#%E6%9A%B4%E5%8A%9B%E8%A7%A3%E6%B3%95）：

代码如下：

　　// 滑动窗口         int sum = 0, res = INT_MAX; 　　//sum为滑动窗口数值之和，res为滑动窗口长度         int l = 0; 　　　　　　　　　　　// 滑动窗口左指针         for(int r = 0; r < nums.size(); r++){ //r为滑动窗口右指针             sum += nums[r]; 　　　　　　// 右指针往右移的同时，更新窗口内数值之和             while(sum >= target){ 　　　　// 在sum > target时，固定右指针，左指针右移，寻找左指针精确位置                 if(r - l + 1 <= res){ 　　　　// 移动过程中，满足条件的窗口，其长度比之前最小长度小时，才更新res                     res = r - l + 1;                 }                 sum -= nums[l++]; 　　　　// 左指针往右移的过程中，要更新sum的值，使其减去移动之前的左指针的值             }         }         // 如果res没有被赋值的话，说明没有符合条件的窗口，返回0，否则返回res         return res == INT_MAX ? 0 : res;