难度：中等。
标签：数组，二分查找，前缀和，滑动窗口。
动态规划写了一遍，没提交，肯定超时。
代码：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(n));
for(int i = 0; i < n; ++i){
dp[i][i] = nums[i];
if(dp[i][i] >= target)return 1;
}
for(int step = 1; step < n; ++step){
for(int i = 0; i < n - step; ++i){
int j = i + step;
dp[i][j] = nums[j] + dp[i][j - 1];
if(dp[i][j] >= target)return step + 1;
}
}
return 0;
}
};
看了标签，使用二分查找，于是有了如下题解。先把前缀和存成一个数字，然后遍历sums作为左边界，查找大于等于target的有边界。
正确解法：
class Solution {
int findNum(vector<int>& arr, int target, int left, int right){
int l = left, r = right, ans = right + 1;
while(l <= r){
int mid = (l + r) / 2;
if(arr[mid] >= target){
ans = mid;
r = mid - 1;
}
else{
l = mid + 1;
}
}
return ans;
}
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
vector<int> sums(n + 1);
sums[0] = 0;
for(int i = 1; i <= n; ++i){
sums[i] = sums[i - 1] + nums[i - 1];
}
int ans = n + 1;
for(int i = 0; i <= n; ++i){
int find = sums[i] + target;
int idx = findNum(sums, find, i + 1, n);
if(idx <= n)ans = min(ans, idx - i);
}
return (ans == n + 1) ? 0 : ans;
}
};
结果：
看了题解，使用滑动窗口来做。
正确解法：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int ans = n + 1;
int l = 0, r = -1, sum = 0;
while(r < n){
if(sum < target){
r++;
if(r >= n)break;
sum += nums[r];
}
else if(sum >= target){
ans = min(ans, r - l + 1);
sum -= nums[l];
l++;
}
}
return (ans == n + 1) ? 0 : ans;
}
};
结果：
