題目描述

給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 。

找出該數(shù)組中滿足其和 ≥ target 的長(zhǎng)度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長(zhǎng)度。如果不存在符合條件的子數(shù)組，返回 0 。

示例：

輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2

輸入：target = 4, nums = [1,4,4]
輸出：1

題解

思路分析

題目要求我們找到和 >= target 的 最小 且 連續(xù) 的子數(shù)組，我們很容易想到暴力枚舉的方法，即訪問數(shù)組的每一個(gè)元素i，并將i作為第一個(gè)元素，向后尋找

暴力枚舉代碼

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            int sum = 0;
            //向后遍歷找到以nums[i]為起始元素的最小數(shù)組
            for(int j = i; j < nums.length;j++){
                sum += nums[j];
                if(sum >= target){
                     //更新目標(biāo)值 由于count的初始值為0，因此需要更新初始值，
                     //否則最小值恒為0
                    if(count > j-i+1 || count == 0){
                        count = j-i+1;
                    }
                    break;
                }
            }
        }
        //若count未被更新，則返回0，即沒有子數(shù)組的和大于target，
        //若count被跟新，則返回最小的子數(shù)組長(zhǎng)度
        return count;
    }
}

此時(shí)我們通過遍歷訪問了數(shù)組的每個(gè)元素，在訪問每個(gè)元素時(shí)，以該元素為起始元素，并向后尋找其最小長(zhǎng)度的子數(shù)組，因此時(shí)間復(fù)制度為O()

而，題目所給的數(shù)組中所有元素均是正整數(shù)，因此每加上一個(gè)元素，子數(shù)組的和 sum 增加，通過這個(gè)特性，我們可以想到使用滑動(dòng)窗口來解決這個(gè)問題

什么是滑動(dòng)窗口？

滑動(dòng)窗口是一種基于雙指針的思想，兩個(gè)指針指向的元素之間形成了一個(gè)窗口

因此滑動(dòng)窗口是通過兩個(gè)指針來維護(hù)的，那么如何移動(dòng)這兩個(gè)指針，是使用滑動(dòng)窗口解決問題的關(guān)鍵

 初始時(shí)，兩個(gè)指針都指向0下標(biāo)位置

遍歷元素，若條件不滿足，則將right指針向右移動(dòng)，直到條件滿足為止

當(dāng)條件滿足時(shí)，則保持右指針不變，開始移動(dòng)左指針 left

在向窗口中添加新元素或從窗口中刪除舊元素時(shí)，可能會(huì)更新一些與窗口范圍有關(guān)的數(shù)據(jù)（例如，本題就需要更新最小子數(shù)組的長(zhǎng)度）

如何使用滑動(dòng)窗口解決本題？ 

（1）我們定義兩個(gè)指針left right，并讓其都指向數(shù)組首元素

（2）此時(shí)窗口內(nèi)只有 2 這一個(gè)元素，不滿足和 sum >= target，因此將right向右移動(dòng)，將新的元素加入窗口中，并判斷此時(shí)子數(shù)組的和 sum 是否大于等于target，若滿足，則不再移動(dòng)right

（3）在sum >= target時(shí)，首先判斷最小的子數(shù)組長(zhǎng)度是否需要更新，并保持right不變，向右移動(dòng)左指針left，刪除舊的元素，直到sum < target

（4）循環(huán)（2）（3），直到right遍歷完數(shù)組

為什么可以使用滑動(dòng)窗口解決本題？

因?yàn)槲覀円业淖訑?shù)組是連續(xù)的，且數(shù)組中的元素都為正整數(shù)，即子數(shù)組中增加一個(gè)元素，子數(shù)組中的元素和sum增加，從窗口中刪除一個(gè)元素，sum減小，因此我們可以通過改變子數(shù)組的兩端元素來更新數(shù)組，因此可以使用滑動(dòng)窗口來解決本題

由于左右指針都只遍歷了一遍數(shù)組，因此時(shí)間復(fù)雜度為O(N)

滑動(dòng)窗口代碼

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = nums[0];
        int len = nums.length;
        int count = 0;
        while(left <= right && right < len){
            //小于目標(biāo)值，向右移動(dòng)右指針right
            while(left <= right && right < len && sum < target){
                right++;
                if(right == len){
                    break;
                }
                sum += nums[right];
            }
            //大于等于目標(biāo)值
            while(left <= right && sum >= target){
                //更新目標(biāo)值 由于count的初始值為0，因此需要更新初始值，否則最小值恒為0
                if((right - left) < count || count == 0){
                    count = right - left + 1;
                }
                //左邊值出窗口，left向右移動(dòng)
                sum -= nums[left];
                left++;
            }
        }
        //若count未被更新，則返回0，即沒有子數(shù)組的和大于target，
        //若count被跟新，則返回最小的子數(shù)組長(zhǎng)度
        return count;
    }
}

題目來自：

LCR 008. 長(zhǎng)度最小的子數(shù)組 - 力扣（LeetCode）

總結(jié)

到此這篇關(guān)于長(zhǎng)度最小的子數(shù)組題目的文章就介紹到這了,更多相關(guān)Java長(zhǎng)度最小的子數(shù)組內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論