雙指針 長(zhǎng)度最小的子數(shù)組

題目

給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s ，找出該數(shù)組中滿(mǎn)足其和 ≥ s 的長(zhǎng)度最小的連續(xù)子數(shù)組，并返回其長(zhǎng)度。如果不存在符合條件的連續(xù)子數(shù)組，返回 0。

示例:

輸入: s = 7, nums = [2,3,1,2,4,3] 輸出: 2 解釋: 子數(shù)組 [4,3] 是該條件下的長(zhǎng)度最小的連續(xù)子數(shù)組。

進(jìn)階:

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

解法一

1.從nums[0]開(kāi)始，一直累加，當(dāng)>=s之后統(tǒng)計(jì)位數(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é)：這也是雙指針的思想，但是卻很高的時(shí)間空間復(fù)雜度

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

原因在于

1. 多個(gè)if判斷

2. 后面的指針沒(méi)有必要再往從i開(kāi)始加，因?yàn)橹暗囊粋€(gè)sum才剛剛大過(guò)s;現(xiàn)在去掉第一個(gè)數(shù)字之后，如果小于前面也必然小于

解法二 ：改進(jìn)

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;
    }
}

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