題目: LeetCode 209. 長度最小的子數(shù)組
給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長度最小的連續(xù)子數(shù)組伴网。如果不存在符合條件的連續(xù)子數(shù)組，返回 0跪者。
示例:
輸入: s = 7, nums = [2,3,1,2,4,3]
輸出: 2
解釋: 子數(shù)組 [4,3] 是該條件下的長度最小的連續(xù)子數(shù)組。
// 暴力解法
// 該方法在 Leetcode 中會超時厦滤！
// 時間復(fù)雜度: O(n^3)
// 空間復(fù)雜度: 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 ;
}
// 優(yōu)化暴力解
// 時間復(fù)雜度: O(n^2)
// 空間復(fù)雜度: 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 ;
}
// 滑動窗口的思路
// 時間復(fù)雜度: O(n)
// 空間復(fù)雜度: 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;
}
