題目描述

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

示例:

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

進階:

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

分析

這一題有3種方法可以做出來，分別是：

• 暴力破解
• 二分查找
• 雙指針

我是在探索欄目中，學習雙指針的時候第一次遇到這個題目的，所以本文只分析了雙指針方法的解題思路。以后有機會再加上其他的思路。

雙指針法

雙指針的核心思想就是要維護兩個指針：一個快指針和一個慢指針，并確定兩個指針的移動策略。有了這個思路，再想一下這個題目里面雙指針的移動策略應該怎么確定。

首先可以將元素盡量多地累計起來，讓它們的和超過s，再按數組的索引，從小到大去掉一些元素，使元素和逼近s，并保持元素和大于等于s。這個時候，通過一左一右兩個指針（索引）就可以計算出最小連續(xù)數組的長度。

源碼

public int minSubArrayLen(int s, int[] nums)
{
    int len = nums.length;
    int ans = Integer.MAX_VALUE;
    int left = 0;
    int sum = 0;
    for (int i = 0; i < len; i++)
    {
        sum += nums[i]; // 把前i個元素累加起來
        while (sum >= s)
        {
            ans = Math.min(ans, i - left + 1);
            sum -= nums[left++]; // 依次剔除元素，使sum盡量接近s
        }
    }
    return (ans != Integer.MAX_VALUE)? ans : 0;
}

測試用例

public static void main(String[] args)
{
    MinimumSizeSubarraySum msss = new MinimumSizeSubarraySum();
    int[] a = {2,3,1,2,4,3};
    int s = 7;
    int b = msss.minSubArrayLen(s,a);
    System.out.println(b);
}

輸出：2