给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。c++代码
时间: 2024-01-21 07:20:13 浏览: 105
以下是使用双指针的 C++ 代码实现:
```c++
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int left = 0, right = 0, sum = 0, ans = INT_MAX;
while (right < n) {
sum += nums[right];
while (sum >= target) {
ans = min(ans, right - left + 1);
sum -= nums[left++];
}
right++;
}
return ans == INT_MAX ? 0 : ans;
}
};
```
我们维护双指针 `left` 和 `right`,它们表示当前子数组的左右端点。初始时,它们都指向下标 0。然后,我们不断地增加 `right` 指针来扩张子数组,同时不断地增加 `left` 指针来收缩子数组,直到子数组的和不小于 `target`。
具体来说,我们先增加 `right` 指针,将当前元素加入子数组中。如果此时子数组的和不小于 `target`,则更新答案;否则继续增加 `right` 指针。当子数组的和不小于 `target` 时,我们开始增加 `left` 指针,将左端点对应的元素从子数组中移除,并更新答案。然后继续增加 `left` 指针,直到子数组的和小于 `target`,此时继续增加 `right` 指针。
最终,我们得到的答案就是最小的满足条件的子数组长度。如果不存在符合条件的子数组,返回 0。
阅读全文