一、題目

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

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

二、示例

2.1> 示例 1：

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

2.2> 示例 2：

【輸入】target = 4, nums = [1,4,4]
【輸出】1

2.3> 示例 3：

【輸入】target = 11, nums = [1,1,1,1,1,1,1,1]
【輸出】0

提示：

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

三、解題思路

根據(jù)題目描述我們要找出該數(shù)組中滿足其和大于等于target的長(zhǎng)度最小的連續(xù)子數(shù)組。那么對(duì)于“連續(xù)子數(shù)組”這個(gè)關(guān)鍵點(diǎn)，我們很容易就會(huì)想到能否采用滑動(dòng)窗口來解決這道題。

而題目中的另一個(gè)關(guān)鍵點(diǎn)——連續(xù)子數(shù)組其和需要大于等于target，那么就可以理解為變化窗口大小的依據(jù)了，具體規(guī)則如下所示：

【規(guī)則1】如果連續(xù)子數(shù)組其和 大于等于 target，則擴(kuò)大窗口的右側(cè)部分；
【規(guī)則2】如果連續(xù)子數(shù)組其和 小于 target，則縮小窗口的左側(cè)部分；

隨著遍歷結(jié)束，我們返回滿足上述條件中最小長(zhǎng)度即可；在解題過程中，我們可以采用雙指針的方式來模擬滑動(dòng)窗口。那么以上就是本題的解題思路了，為了便于大家理解，我們一下以輸入 target = 7, nums = [2,3,1,2,4,3]為例，看一下具體的操作流程是怎么樣的。具體請(qǐng)見下圖所示：

四、代碼實(shí)現(xiàn)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int i = 0, j = 0, sum = nums[0], result = 100001;
        while(true) {
            if (sum < target) {
                if (j >= nums.length - 1) break;
                sum += nums[++j]; // 向右移動(dòng)右指針
            } else {
                result = Math.min(result, j - i + 1); 
                sum -= nums[i++]; // 向右移動(dòng)左指針
            }
        }
        return result == 100001 ? 0 : result;
    }
}

今天的文章內(nèi)容就這些了：

寫作不易，筆者幾個(gè)小時(shí)甚至數(shù)天完成的一篇文章，只愿換來您幾秒鐘的 點(diǎn)贊 & 分享 。

更多技術(shù)干貨，歡迎大家關(guān)注公眾號(hào)“爪哇繆斯” ~ \(^o)/ ~ 「干貨分享，每天更新」