看了卡哥的视频后,写了如下代码:
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0;
int i = 0, j = 0;
for (j = 0; j < nums.size(); j ++ )
{
sum += nums[j];
while (sum >= target)
{
result = min(result, j - i + 1);
sum -= nums[i ++ ];
}
}
return result == INT32_MAX ? 0 : result;
}
};
几个注意点:
-
因为是求最小值,所以将
result
初始化为INT32_MAX
,同时与min
函数配合,求出答案。 -
注意此题的
i
不会回溯,i
是一直向前走的,j
是一直向后走的。为什么
i
是一直向前走的?当改变
j
的值时(即j ++
),i
不会重新赋值为0,因为我们要求的是长度最小的子数组,将i
赋值为0没有意义(为什么没意义?因为从0到还没赋值为0的那个i
都不会导致比上一个result
更优的result
,应该从还没赋值为0的那个i
的后一个位置开始考虑) -
应该是
while (sum >= target)
而不是while (sum > target)
因为
sum == target
的时候对应的i
,j
可能对应着答案,我们要让sum == target
这个情况进入while处理。