雙指針 長度最小的子數(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ù)組。

進階:

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

解法一

1.從nums[0]開始，一直累加，當>=s之后統(tǒng)計位數(shù)i+1-j 2.回到nums[1]繼續(xù)上一步操作

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int i=0,l=nums.length,j=0;
        int min=9999;
        int sum=0;
        if(l==0) return 0;
        sum=nums[0];
        if (sum>=s) return 1;
        for (i=1;i<l;i++){
            
            sum+=nums[i];
            if(sum>=s){
                    min=Math.min(min,i+1-j);
                    
                    j++;
                    i=j;
                    sum=nums[j];
                    if (sum>=s) return 1;
                
            }
        }
        if(min==9999) min=0;
        return min;
    }
}

總結(jié)：這也是雙指針的思想，但是卻很高的時間空間復(fù)雜度

時間復(fù)雜度O（nlogn)

原因在于

1. 多個if判斷

2. 后面的指針沒有必要再往從i開始加，因為之前的一個sum才剛剛大過s;現(xiàn)在去掉第一個數(shù)字之后，如果小于前面也必然小于

解法二 ：改進

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) {
            sum += nums[end];
            while (sum >= s) {
                ans = Math.min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

時間復(fù)雜度O(N)