給定一個含有?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ù)組。
進階:

如果你已經(jīng)完成了O(n) 時間復雜度的解法, 請嘗試?O(n log n) 時間復雜度的解法。

思路：

雙指針法：

設定上下界，從0開始，右指針一直向右遍歷，累加遍歷過的值，當和大于等于s時，減去第一個值，如果還是大于等于s，減去第二個值，以此類推，一直遍歷到最后。

提交的代碼：

class Solution {
? ? public int minSubArrayLen(int s, int[] nums) {
? ? ? ? int i=0,j=0,sum=0,t=2147483647;//sum記錄當前和，t記錄當前和是幾個值的相加
?? ??? ? while(sum>=s||(i<nums.length&&j<nums.length))? ?//這里sum>=s比較重要，比如s=7，數(shù)組最后三項是2，4，3，如果不加，因為此時j已經(jīng)達到退出循環(huán)的條件，會退出，然后sum=9，t=3；所以加這個條件使得繼續(xù)執(zhí)行else if中的操作
?? ??? ? {
?? ??? ??? ? if(sum<s)
?? ??? ??? ? {
?? ??? ??? ??? ? sum+=nums[j];
?? ??? ??? ??? ? j++;
?? ??? ??? ? }
?? ??? ??? ? else if(sum>=s)
?? ??? ??? ? {
?? ??? ??? ??? ? if(j-i<t)
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? t = j-i;
?? ??? ??? ??? ? }
?? ??? ??? ??? ? sum-=nums[i];
?? ??? ??? ??? ? i++;
?? ??? ??? ? }
?? ??? ? }
?? ??? ? if(t==2147483647)
?? ??? ? {
?? ??? ??? ? return 0;
?? ??? ? }
?? ? ? ? ?return t; ?
? ? }
}

完整的代碼：

public class Solution209 {
?? ? public static int minSubArrayLen(int s, int[] nums) {
?? ??? ? int i=0,j=0,sum=0,t=2147483647;//sum記錄當前和，t記錄當前和是幾個值的相加
?? ??? ? while(sum>=s||(i<nums.length&&j<nums.length))
?? ??? ? {
?? ??? ??? ? if(sum<s)
?? ??? ??? ? {
?? ??? ??? ??? ? sum+=nums[j];
?? ??? ??? ??? ? j++;
?? ??? ??? ? }
?? ??? ??? ? else if(sum>=s)
?? ??? ??? ? {
?? ??? ??? ??? ? if(j-i<t)
?? ??? ??? ??? ? {
?? ??? ??? ??? ??? ? t = j-i;
?? ??? ??? ??? ? }
?? ??? ??? ??? ? sum-=nums[i];
?? ??? ??? ??? ? i++;
?? ??? ??? ? }
?? ??? ? }
?? ??? ? if(t==2147483647)
?? ??? ? {
?? ??? ??? ? return 0;
?? ??? ? }
?? ? ? ? ?return t; ?
?? ? ? ?}
?? ? public static void main(String[] args)
?? ? {
?? ??? ? int[] nums = {2,3,1,2,4,3};
?? ??? ? int s = 7;
?? ??? ? System.out.println(minSubArrayLen(s,nums));
?? ? }
}
?

總結

以上是生活随笔為你收集整理的Leetcode--209. 长度最小的子数组的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。