长度最小的子数组 Minimum Size Subarray Sum

题目: LeetCode 209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
// 暴力解法
// 该方法在 Leetcode 中会超时！
// 时间复杂度: O(n^3)
// 空间复杂度: O(1)
public static int minSubArrayLen1(int s, int[] nums) {
if(s <= 0 || nums == null){
throw new IllegalArgumentException("Illigal Arguments");
}
int res = nums.length + 1;
for(int l = 0;l< nums.length;l++){
for(int r = l;r<nums.length;r++){
int sum = 0;
for(int i = l;i<=r;i++){
sum = sum + nums[i];
}
if(sum >= s){
res = Math.min(res,r - l + 1);
}
}
}
if(res == nums.length + 1){
return 0;
}
return res ;
}

// 优化暴力解
// 时间复杂度: O(n^2)
// 空间复杂度: O(n)
public static  int minSubArrayLen2(int s, int[] nums) {
    if(s <=0 || nums == null){
        throw new IllegalArgumentException("Illigal Arguments");
    }
    int[] sums = new int[nums.length + 1];
    sums[0] = 0;
    for(int i = 1;i<=nums.length;i++){
        sums[i] = sums[i-1] + nums[i-1];
    }
    int res = nums.length + 1;
    for(int l = 0;l< nums.length;l++){
        for(int r = l;r<nums.length;r++){
            if(sums[r+1] - sums[l] >= s){
                res = Math.min(res,r - l + 1);
            }
        }
    }
    if(res == nums.length + 1){
        return 0;
    }
    return res ;
}

// 滑动窗口的思路

// 时间复杂度: O(n)
// 空间复杂度: O(1)
public static int minSubArrayLen3(int s, int[] nums) {
if(s <=0 || nums == null){
throw new IllegalArgumentException("Illigal Arguments");
}
int l =0 ;
int r = -1;
int res = nums.length + 1;
int sums = 0;
while(l < nums.length){
if(r + 1<nums.length&&sums<s){
sums += nums[++r];
}else{
sums -= nums[l++];
}
if(sums >= s){
res = Math.min(res,r - l + 1);
}
}
if(res == nums.length + 1){
return 0;
}
return res;
}