209. 长度最小的子数组

思路:动态规划。

我原本想着能不能用单序列动态规划来做。但是这样有个问题,就是只能记录一个下标状态,所以只适用于子序列问题。我们需要记录连续的下标,至少要有一个开始下标和一个结束下标。据此,可以自己和自己组合状态,适用双序列模型。

如下:每行计算达到 target 时的 长度(j-i+1),找出其中最小的。

image-20211118122024227

$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;
  }
};