209.minimum-size-subarray-sum.md

209. 长度最小的子数组

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

两种方法

1. 暴力。时间O(n²)

   class Solution {
   public:
       int minSubArrayLen(int s, vector<int>& nums) {
           int i,j, sum=0, res=INT_MAX;
           for(i=0; i<nums.size(); i++)
           {
               sum = nums[i];
               if(sum>=s)
                   return 1;
               for(j=i+1; j<nums.size(); j++)
               {
                   sum += nums[j];
                   if(sum>=s)
                   {
                       res = min(res, j-i+1);
                       break;
                   }
                       
               }
           }
           return res==INT_MAX? 0: res;
       }
   };
   

2. 滑动窗口(双指针)。时间O(n)
   • 思路
     • i是窗口起点，j是窗口终点。i、j初始位置都是0。
     • sum保存从i到j的累加和。
     • 如果sum<s，终点j就一直向右侧拓展。
     • 如果sum>=s，记录窗口size值，每次更新最小值。 起点i一直向右侧移动(收缩窗口)。 同时将sum中的nums[i]减去。
   • 实现

   class Solution {
   public:
       int minSubArrayLen(int s, vector<int>& nums) {
           int window_size=INT_MAX, i=0, j=0, sum=0;
           for(;j<nums.size();)
           {    
               {
                   sum += nums[j];
                   j++;
               } 
               while(sum>=s){
                   window_size = min(window_size, j-i);
                   sum -= nums[i];
                   i++;
               }
                                                                       
           }
           return window_size==INT_MAX? 0: window_size;
       }
   };