# 【LeetCode刷題】【演算法學習筆記】209. Minimum Size Subarray Sum
* 學習時間：2025/01/30 (Fir.)
* **題目連結（美服）：** [209. Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/description/)
* **題目連結（國服）：**[209. 长度最小的子数组](https://leetcode.cn/problems/minimum-size-subarray-sum/description/)
* **題目標籤：** ==陣列== ==前綴和== ==二分搜尋== ==[滑動視窗](https://hackmd.io/@SupportCoding/Sliding_Window)==
* **解題影片：**[拿下滑动窗口！ | LeetCode 209 长度最小的子数组](https://www.bilibili.com/video/BV1tZ4y1q7XE/?vd_source=e0b39ef55fea35a347aa1da490ac5b01) [滑动窗口【基础算法精讲 03】](https://www.bilibili.com/video/BV1hd4y1r7Gq/?vd_source=e0b39ef55fea35a347aa1da490ac5b01)

### A. 題目 (原文)
---
>Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray
whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

>Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

>Constraints:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

### B. 題意（中文）
---
>给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的
子数组
[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

>示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

>提示：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

### C. 參考程式碼
---
:::spoiler Solution

# reference: 灵茶山艾府(https://leetcode.cn/problems/search-insert-position/solutions/2023391/er-fen-cha-zhao-zong-shi-xie-bu-dui-yi-g-nq23/)

:::

:::spoiler Thinking（思路）
reference: [力扣官方题解](https://leetcode.cn/problems/search-insert-position/solutions/333632/sou-suo-cha-ru-wei-zhi-by-leetcode-solution/) [灵茶山艾府](https://leetcode.cn/problems/search-insert-position/solutions/2023391/er-fen-cha-zhao-zong-shi-xie-bu-dui-yi-g-nq23/)
#### 滑動窗口
💡 滑動窗口解說 ➡︎ [滑动窗口【基础算法精讲 03】](https://www.bilibili.com/video/BV1hd4y1r7Gq/?vd_source=e0b39ef55fea35a347aa1da490ac5b01)
1. **概念**
* 定義兩個指針 **start** **and** ☞ 滑動窗口的**窗口**，即是 子數組的開始位置和結束位置
* sum 儲存子數组中的元素和 ☞ 即是 nums[start] 到 nums[end]元素和
2. **程式碼實現**
* 初始化 ➡︎ start, end, sum 設為 **0**
* 遞迴過程
* 每輪將 nums[end] 加入 sum
* 若 sum ≥ s，更新 最小子數組長度 (end - start + 1)（區間從 0 開始所以+1）
* 縮小窗口
➡︎ 窗口滿足條件 (sum ≥ s)，此時 start 指向窗口的左端，end 指向右端。
➡︎ 更新最小長度：計算當前窗口的長度 end - start + 1，如果比之前找到的最小長度更短，則更新最小值。
* 從 sum 中 減去 nums[start]（移除窗口左端的元素）。
* start 右移 一位 (start += 1)
* 檢查新的 sum 是否仍然滿足 ≥ s，如果滿足，繼續更新最小長度，並繼續縮小窗口，**直到 sum < s**。
* 最後 end 右移，進入下一輪
3. 舉例：
* target = 7
* nums = [2,3,1,2,4,3]
* right（右端）怎麼移動 ☞

| right | nums[right] | **s（總和）** | left 調整 | ans 更新 |
| ----- | ----------- | --------- | --------- | -------- |
| 0 | 2 | 2 | | |
| 1 | 3 | 5 | | |
| 2 | 1 | 6 | | |
| 3 | 2 | 8(2,3,1,4)| 1 |4(3,1,2,4)|
| 4 | 4 | 10 | 2 |3(2,4,3) |
| 5 | 3 | 7 | 3 |2(4,3) |

💡 不斷循環，當 s ≥ target
☞ sum -= nums[ left ]
☞ left += 1; right += 1
☞ 當前長度: end - start + 1