https://leetcode.com/problems/minimum-size-subarray-sum/description/
209. Minimum Size Subarray Sum
給你一個陣列 nums 和一個數字 target，找出最小的連續子序列長，該子序列的和
需要大於等於 target（不能的話返回0）。
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
思路：
1.因為子序列是連續的所以直覺的想到滑動窗口，每次都先push一個數字，直到和大於
target為止。
2.當和大於等於target時，檢查pop掉最左邊的數字時是否也可以滿足 sum >= target，
如果可以就一直 pop 掉窗口最左元素直到不滿足。
3.承2，pop到不能pop之後，再用目前的最小窗口長度更新答案。
Java Code：
-------------------------------------
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int res = Integer.MAX_VALUE;
int l = 0;
int r = 0;
int sum = 0;
while (r < nums.length) {
sum += nums[r];
if (sum >= target) {
while (sum - nums[l] >= target) {
sum -= nums[l++];
}
res = Math.min(res, r - l + 1);
}
r++;
}
return res == Integer.MAX_VALUE ? 0 : res;
}
}
-------------------------------------
--
https://i.imgur.com/YPBHGGE.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1688837580.A.870.html
※ 編輯: Rushia (122.100.75.86 臺灣), 07/09/2023 01:34:53