33 lines
1.1 KiB
C++
33 lines
1.1 KiB
C++
#include "s0209_minimum_size_subarray_sum.hpp"
|
|
|
|
int S0209::minSubArrayLen(int target, vector<int>& nums) {
|
|
int len = nums.size();
|
|
int result{INT_MAX};
|
|
for (int begin{0}, end{0}, sum{0}; end < len; ++end) {
|
|
sum += nums[end];
|
|
// 当滑动窗口里的值的总和大于等于 target 时，移动 begin 直到 sum 比 target
|
|
// 小
|
|
if (sum >= target) {
|
|
while (begin < end && sum >= target) {
|
|
sum -= nums[begin];
|
|
++begin;
|
|
}
|
|
// 循环结束后有以下几种情况
|
|
// 1. begin == end && sum >= target 此时 result == 1
|
|
// 2. begin == end && sum < target 此时 result == 2
|
|
// 3. begin < end && sum < target 此时 result == end - begin + 2
|
|
int tmp;
|
|
if (begin == end) {
|
|
tmp = sum >= target ? 1 : 2;
|
|
} else {
|
|
tmp = end - begin + 2;
|
|
}
|
|
// 更新 result
|
|
result = tmp < result ? tmp : result;
|
|
}
|
|
}
|
|
// 如果 result == INT_MAX 说明 result
|
|
// 从来没更新过，也就意味着即使所有数组元素加在一起也比 target 小，此时返回 0
|
|
return result == INT_MAX ? 0 : result;
|
|
}
|