209. 长度最小的子数组
思路:动态规划。
我原本想着能不能用单序列动态规划来做。但是这样有个问题,就是只能记录一个下标状态,所以只适用于子序列问题。我们需要记录连续的下标,至少要有一个开始下标和一个结束下标。据此,可以自己和自己组合状态,适用双序列模型。
如下:每行计算达到 target 时的 长度(j-i+1),找出其中最小的。
$f (i,j)$ 表示切片 $v [i:j]$ 的元素之和。
递推关系:$f (i,j) = f (i,j-1) + v [j]$,可以看到和 $i-1$ (上一行)没啥关系,可以简化为 $f (j) = f (j-1) + v [j]$,减少空间复杂度。
class Solution {
public:
// 4, {1,4,4}
int minSubArrayLen(int target, vector<int> &v) {
int n = v.size();
std::vector<int> dp(n, 0);
int minlen = 0x3f3f3f3f;
for (int i = 0; i < n; i++) {
dp[i] = v[i];
if (dp[i] >= target) {
return 1;
}
for (int j = i + 1; j < n; j++) {
dp[j] = dp[j - 1] + v[j];
auto len = j - i + 1;
if (dp[j] >= target && len < minlen) {
minlen = len;
}
}
}
if (minlen == 0x3f3f3f3f) {
return 0;
}
return minlen;
}
};
然而超时了…… 说明时间复杂度有待优化。
不能否认的是,这题必须要知道两个坐标。上面的方法,问题在于每次都要 dp [j] = dp [j - 1] + v [j]
与 v [j]
求和浪费了时间。因此不如用双指针。
双指针可以从两端开始,也可以从一端开始。
- 如果从两端开始,那么容易陷入局部最优,因为没法遍历所有的子区间。
所以用左端开始的双指针。左指针右移就减少,右指针右移就增加,直到收敛到合适范围。
class Solution {
public:
int minSubArrayLen(int target, vector<int> &v) {
int n = v.size();
if (n == 0) {
return 0;
}
int l = 0, r = 0;
int minlen = INT_MAX;
size_t sum = v[0];
while (l <= r && r < n) {
if (sum >= target) {
minlen = min(minlen, r - l + 1);
sum -= v[l];
l++;
} else {
r++;
if (r != n)
sum += v[r];
}
}
return minlen == INT_MAX ? 0 : minlen;
}
};