问题描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsₗ, numsₗ+₁, ..., numsr-₁, 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 <= 10⁹1 <= nums.length <= 10⁵1 <= nums[i] <= 10⁵
进阶：
- 如果你已经实现
O(n)时间复杂度的解法, 请尝试设计一个O(n log(n))时间复杂度的解法。
解题思路
滑动窗口
如果sum < target，sum += nums[right++]，即右指针右移，扩大窗口；否则更新min_len，sum -= nums[left]，左指针右移，缩小窗口
前缀和+二分
因为这里要考虑的是连续子数组的和，因此很容易想到前缀和，这里数组中的数都大于0，所以前缀和数组单调递增，因此可以考虑使用二分查找，来找到小于或等于prefix[j] - target的最大的prefix[i]，所求即为\((j - i)_{\min}\)
代码
滑动窗口
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left = 0, right = 0;
int sum = 0;
int min_len = nums.size() + 1;
while (right < nums.size()) {
while (sum < target && right < nums.size()) {
sum += nums[right++];
}
while (sum >= target && left <= right) {
if (sum >= target) {
min_len = min(min_len, right - left);
}
sum -= nums[left];
left++;
}
}
if (min_len > nums.size()) {
return 0;
}
return min_len;
}
};
前缀和+二分
class Solution {
public:
int BSearch(int idx, int target, vector<int> &prefix) {
int left = 0, right = idx;
// 左闭右开
while (left < right) {
int mid = left + (right - left) / 2;
if (prefix[mid] < prefix[idx] - target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
int minSubArrayLen(int target, vector<int> &nums) {
// 前缀和
int n = nums.size();
vector<int> prefix(n + 1, 0);
for (int i = 1; i <= nums.size(); i++) {
prefix[i] = prefix[i - 1] + nums[i - 1];
}
// 二分查找
int res = n + 1;
for (int i = 1; i <= n; i++) {
int j = BSearch(i, target - 1, prefix);
if (prefix[i] >= target) {
res = std::min(i - j + 1, res);
}
}
if (res == n + 1) {
return 0;
}
return res;
}
};