LeetCode209. 长度最小的子数组

题目

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

代码

法一、直接暴力

 1 class Solution {
 2 public:
 3     int minSubArrayLen(int s, vector<int>& nums) {
 4         int min = INT_MAX;
 5         for(int i = 0;i < nums.size();i++){
 6             int res = 0;
 7             for(int j = i;j < nums.size();j++){
 8                 res += nums[j];
 9                 if(res >= s ) {
10                    if(min > j-i+1) min = j-i+1;
11                    break;
12                 }
13             }
14         }
15         if(min == INT_MAX) return 0;
16         else return min;   
17     }
18 };

要注意最后的返回值，开始提交的错误的原因：就在没有考虑不存在子序列之和的情况

法二、滑动窗口,，，，重点掌握这种方法

滑动窗口就是双指针算法的一种。

定义变量：窗口的起始位置 start，结束位置 end，窗口的长度 subLength，窗口内数据之和 sum，以及最终结果res

主体思想：

1. 找到满足条件的序列，即窗口。寻找的方法就是终止位置不断右移，直到窗口内元素之和满足条件

2.收缩这个窗口，start后移，查看是否有满足条件的子序列。

　　若满足条件(意味着窗口可以收缩)，则start继续右移，继续检验，直到收缩到最小窗口

　　若不满足条件（意味着需要将窗口整体右移），此时相比于之前的窗口，起始位置后移，终止位置后移，返回1，

　　去找满足条件的窗口

 1 class Solution {
 2 public:
 3     int minSubArrayLen(int s, vector<int>& nums) {
 4         int res = INT_MAX;  //存放结果
 5         int sum = 0;//存放滑动窗口数值之和
 6         int start = 0;//代表窗口的起始位置
 7         int subLength = 0; //滑动窗口的长度
 8 
 9         for(int end = 0;end < nums.size();end++){  
10             //end代表窗口的结束位置
11             sum += nums[end];
12             while(sum >= s){
13                 subLength = (end - start + 1);
14                 res = min(res,subLength);
15                 sum = sum -nums[start];
16                 start++;
17                 
18             }
19 
20         }
21        
22         if(res == INT_MAX) return 0;
23         else return res;   
24     }
25 };

法三、前缀和数组

待更新