# 前言

藉由 LeetCode 磨練演算法

# 題目連結

Minimum Size Subarray Sum - LeetCode

# 解題思路

# 暴力解

藉由兩層 for loop，把每一個 item 都當作起點往右計算 sum，當 sum >= target 時，把 length 記下，若 length < minLen，則 minLen = length

solution code:

<?php
class Solution {

    /**
     * @param Integer $target
     * @param Integer[] $nums
     * @return Integer
     */
    function minSubArrayLen($target, $nums) {
        $minLen = count($nums) + 1;
        $len = count($nums);
        for ($i = 0; $i < $len; $i++) {
            $left = $i;

            $sum = $nums[$left];

            // 如果 $left 即 window 的初始點，$sum 已經 >= $target
            // 則已得出此 item 往右的 minLen，可直接 continue
            if ($sum >= $target) {
                $curLen = 1;
                $minLen = min($curLen, $minLen);
                continue;
            }

            // 如果 $left 已經是最後一個 item，則 window 就只有它自己
            if ($left + 1 === $len) {
                continue;
            }

            $right = $left + 1;

            while ($right < $len) {
                $sum += $nums[$right];

                // 只要 $sum >= $target 代表該 item 為 $left 的 window
                // 已找到 $minLen，就不需要在 while loop 了
                if ($sum >= $target) {
                    $curLen = $right - $left + 1;
                    $minLen = min($curLen, $minLen);
                    break;
                }
                $right++;
            }

        }

        if ($minLen === $len + 1) {
            return 0;
        }

        return $minLen;
    }
}

時間複雜度為 O(N²)，跑了兩層 loop 空間複雜度為 O(1)，都是在維護幾個固定的 variable

• $minLen
• $left
• $right
• $len

# two pointer

使用 two pointer pattern 維護 $left & $right，當 $sum >= $target 時才會去移動 $left pointer，看起來就像是一個 sliding window，當 window length >= $target 時便記下 $curLen，接著比較 $minLen 是否 < $curLen，如果 $curLen 較小，則更新 $minLen

solution code:

<?php
class Solution {

    /**
     * @param Integer $target
     * @param Integer[] $nums
     * @return Integer
     */
    function minSubArrayLen($target, $nums) {
        $left = 0;
        $minLen = count($nums) + 1;
        $len = count($nums);
        $sum = 0;

        for ($right = 0; $right < $len; $right++) {
            $sum += $nums[$right];

            while ($sum >= $target && $right >= $left) {
                $curLen = $right - $left + 1;
                $minLen = min($curLen, $minLen);

                $sum -= $nums[$left];
                $left++;
            }
        }

        if ($minLen === $len + 1) {
            return 0;
        }

        return $minLen;
    }
}

雖然在 for loop 裡面跑一個 while loop，但實際上最差的情況，就是每一個 item 都 >= $target，在這樣的情境下會是 O(2N)，因此

時間複雜度為 O(N) 空間複雜度為 O(1)，這並沒有把 $nums array 計算進去，因為那算是 parameters。實際上有維護的 variable 就以下幾個，而這些 variable 都不會因為 N 變動而增加

• $left
• $minLen
• $len
• $sum