LeetCode——長度最小的子數組（滑動視窗）

題目描述

解題思路

注意：題目讓我們求的是大于等于target的長度最小的子數組，而不是等于。

思路：通過滑動視窗的思想，不斷更新視窗的最小值。

1：初始化滑動視窗

主要定義滑動視窗的左邊界、右邊界、初始最小值、視窗内的和。

// 定義初始最小值
let minLen = Infinity;
// 定義滑動視窗的左邊界
let left = 0;
// 定義滑動視窗的右邊界
let right = 0;
// 定義視窗内的和
let sum = 0;
複制代碼      

2：核心循環體

隻要右邊界沒有走到最後就繼續循環，首先計算視窗内的和，如果大于等于target，則更新最小長度，然後左移左邊界，循環結束再移動右邊界。

// 隻要右邊界沒有走到最後就不終止循環
while (right < nums.length) {
    sum = sum + nums[right];
    // 如果視窗内的和 ≥ target
    while (sum >= target) {
        // 更新視窗的最小長度
        minLen = Math.min(minLen,right-left+1);
        // 更新和
        sum = sum - nums[left];
        left++
    }
    right++;
}
複制代碼      

3：判斷傳回

如果最小長度是無限大，則傳回0，反之傳回最小長度。

minLen = minLen === Infinity ? 0 : minLen
return minLen
複制代碼      

完整代碼

var minSubArrayLen = function (target, nums) {
    // 定義初始最小值
    let minLen = Infinity;
    // 定義滑動視窗的左邊界
    let left = 0;
    // 定義滑動視窗的右邊界
    let right = 0;
    // 定義視窗内的和
    let sum = 0;
    // 隻要右邊界沒有走到最後就不終止循環
    while (right < nums.length) {
        sum = sum + nums[right];
        // 如果視窗内的和 ≥ target
        while (sum >= target) {
            // 更新視窗的最小長度
            minLen = Math.min(minLen,right-left+1);
            // 更新和
            sum = sum - nums[left];
            left++
        }
        right++;
    }
    minLen = minLen === Infinity ? 0 : minLen
    return minLen
};
minSubArrayLen(7,[2,3,1,2,4,3])
複制代碼      

題目反思

遇到題目中帶有連續的字樣，可以優先考慮使用滑動視窗來解決問題，這道題目并不難，和其他的滑動視窗類型的題目解題方法幾乎一緻。