算法|數(shù)組——滑動窗口
引入
給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) target 。
找出該數(shù)組中滿足其和 ≥ target 的長度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長度**。**如果不存在符合條件的子數(shù)組，返回 0 。
示例 1：
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。
示例 2：
輸入：target = 4, nums = [1,4,4]
輸出：1
示例 3：
輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0
解法
暴力解法
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result = Integer.MAX_VALUE;
for(int i = 0; i < nums.length; i++){
int sum = 0;
for(int j = i; j < nums.length; j++){
sum += nums[j];
if(sum >= target){
result = Math.min(result,j - i + 1);
break;
}
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
這種做法可以很容易想到，可是誰想到它…
超時了哈哈????????????????
那么下面我們看看另外一種思路。
滑動窗口
先看示例代碼：
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result = Integer.MAX_VALUE;
int i = 0;
int sum = 0;
int length = 0;
for(int j = 0; j < nums.length; j++){
sum += nums[j];
while(sum >= target){
length = j - i + 1;
result = Math.min(result,length);
sum -= nums[i++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
下面見分析：
還不錯吧????????
文章來源：http://www.zghlxwxcb.cn/news/detail-659090.html
至此先不更個1-2天，哥們要考科四，現(xiàn)在一題都沒看，再不看就寄了????????文章來源地址http://www.zghlxwxcb.cn/news/detail-659090.html
到了這里，關(guān)于【算法|數(shù)組】滑動窗口的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
