209. 長度最小的子數組#
給定一個含有 n 個正整數的數組和一個正整數 target 。
找出該數組中滿足其總和大於等於 target 的長度最小的 連續子數組 ，並返回其長度。如果不存在符合條件的子數組，返回 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
提示：
進階：
- 如果你已經實現
O(n)時間複雜度的解法，請嘗試設計一個O(n log(n))時間複雜度的解法。
雙指針#
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int i = 0, j = 0;
int cur = 0;
int res = INT_MAX;
while (j < n) {
cur += nums[j];
while (cur >= target) {
res = min(res, j - i + 1);
cur -= nums[i];
++i;
}
++j;
}
return res == INT_MAX ? 0 : res;
}
};
前綴和#
區間和應聯想到前綴和。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
vector<int> prev(n + 1, 0);
// prev[i] 表示 nums 下標 [0, i) 的區間和
for (int i = 1; i <= n; ++i) {
prev[i] = prev[i - 1] + nums[i - 1];
}
int res = INT_MAX;
for (int i = 0; i < n; ++i) {
// prev[j] - prev[i] 表示 nums 下標 [i, j) 區間和
// 需要滿足 prev[j] - prev[i] >= target
// 故 prev[j] >= target + prev[i]
int find_val = target + prev[i];
// prev 為非遞增序列，可以使用二分法查找區間右坐標
auto iter = lower_bound(prev.begin(), prev.end(), find_val);
if (iter != prev.end()) {
res = min(res, static_cast<int>(iter - prev.begin()) - i);
// iter 在 prev 的下標比實際需要的多 1（j 為開區間），所以無需再加 1
}
}
return res == INT_MAX ? 0 : res;
}
};