LeetCode 209. Minimum Size Subarray Sum

解法一：

 使用滑动窗口的方式进行求解，在[ i...j]之前滑动：

  当前的sum < s 时，j 窗口增大，并更新

  sum >=s 时，i ，缩小窗口。

代码语言：javascript复制

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
            return 0;
        int i = 0,j = -1 ;   //[i..j] is sliding window
        int res = n  1;
        int sum = 0;
        
        
        while(i < n){
            if( j 1 < n && sum < s ){
                sum  = nums[  j];
            }else{
                 sum = sum - nums[i  ];
            }
            if (sum >= s)
                res = min( res , j-i 1 );   //update now length 
        }
        
        if(res == n 1)   // 
            return 0;
        return res;
    }
};

解法二：

题目中提到，可以思考一种 nlogn 的解放，经过思考发现可以使用二分搜索的方式进行求解，以长度为8为例，先用一个长度为4的窗口从左到右滑动一遍，如果有满足条件的，用长度为2的再进行滑动，如果没有则用长度为6的。以此类推，在此只给出思路。

sum 搜索

0 人点赞