[209. Minimum Size Subarray Sum](https://leetcode.com/problems/minimum-size-subarray-sum/) ### 題目描述 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` <= 10^9^ * 1 <= `nums.length` <= 10^5^ * 1 <= `nums[i]` <= 10^4^ **Follow up:** If you have figured out the `O(n)` solution, try coding another solution of which the time complexity is `O(n log(n))`. ### 解答 #### Javascript ```javascript= function minSubArrayLen(target, nums) { let minLen = Infinity; let sum = 0; let start = 0; for (let i = 0; i < nums.length; i++) { sum += nums[i]; while (sum >= target) { const length = i - start + 1; minLen = Math.min(minLen, length); sum -= nums[start]; start++; } } if (minLen === Infinity) return 0; return minLen; } ``` > 一年多前寫過,現在寫還是錯了一次才過== > [name=Marsgoat][time=Jul 6, 2023] #### C# ```csharp= public class Solution { public int MinSubArrayLen(int target, int[] nums) { int sum = 0; int min = int.MaxValue; int left = 0; for (int right = 0; right < nums.Length; right++) { sum += nums[right]; while (sum >= target) { min = Math.Min(min, right - left + 1); sum = sum - nums[left++]; } } return min == int.MaxValue ? 0 : min; } } ``` > [name=Jim][time=Jul 6, 2023] #### Python ```python= class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: i, j, total = 0, 0, 0 n = len(nums) ans = float('inf') while j < n: total += nums[j] j += 1 while total >= target: ans = min(ans, j - i) total -= nums[i] i += 1 return ans if ans <= n else 0 ``` > [name=Yen-Chi Chen][time=Thu, Jul 6, 2023] ### Java ```java= class Solution { public int minSubArrayLen(int target, int[] nums) { int windowStart = 0; int ans = Integer.MAX_VALUE; int sum = 0; for (int windowEnd = 0; windowEnd < nums.length; windowEnd++) { sum += nums[windowEnd]; while (sum >= target) { ans = Math.min(ans, windowEnd - windowStart + 1); sum -= nums[windowStart]; windowStart += 1; } } return ans != Integer.MAX_VALUE ? ans : 0; } } ``` > [name=Ron Chen][time=Thu, Jul 6, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)