快捷導(dǎo)航

長度最小的子數(shù)組題目詳解(Java版)

更新時間：2023年12月26日 16:02:33 作者：楠枬

這篇文章主要給大家介紹了關(guān)于長度最小的子數(shù)組(Java版)的相關(guān)資料,這到題來自力扣,通過學(xué)習(xí)本文對大家理解這道題目有很大的幫助,需要的朋友可以參考下

題目描述

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

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

示例：

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

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

題解

思路分析

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

暴力枚舉代碼

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ù)組長度
        return count;
    }
}

此時我們通過遍歷訪問了數(shù)組的每個元素，在訪問每個元素時，以該元素為起始元素，并向后尋找其最小長度的子數(shù)組，因此時間復(fù)制度為O( $^{_N{2}}$ )

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

什么是滑動窗口？

滑動窗口是一種基于雙指針的思想，兩個指針指向的元素之間形成了一個窗口

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

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

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

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

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

如何使用滑動窗口解決本題？

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

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

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

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

為什么可以使用滑動窗口解決本題？

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

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

滑動窗口代碼

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)值，向右移動右指針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向右移動
                sum -= nums[left];
                left++;
            }
        }
        //若count未被更新，則返回0，即沒有子數(shù)組的和大于target，
        //若count被跟新，則返回最小的子數(shù)組長度
        return count;
    }
}

題目來自：

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