LC209.长度最小的子数组

原题链接
image.png

思路1：滑动窗口

  • 此题可以当做滑动窗口的模板题，非常典型，希望熟读他人代码，清楚滑动窗口的一般逻辑。

    代码1：

    1. class Solution {
    2. public:
    3.   int minSubArrayLen(int target, vector<int>& nums) {
    4.       int left = 0, right = 0;
    5.       int n = nums.size();
    6.       int cur_sum = 0;
    7.       int min_len = 0x3f3f3f3f;
    8.       while (right < n) {
    9.           cur_sum += nums[right];
    10.           while (cur_sum >= target) {
    11.               cur_sum -= nums[left];
    12.               min_len = min(min_len, right - left + 1);
    13.               left += 1;
    14.           }
    16.           right += 1;
    17.       }
    19.       return min_len == 0x3f3f3f3f ? 0 : min_len;
    20.   }
    21. };

    思路2：二分查找

  • 变成前缀和summ

  • 对于下标为x的summ[x]而言，其右边一定有一个数summ[y]，满足summ[y]是summ[y] - summ[x] >= target的第一个数，那么子数组长度就是y - x

  • 相当于找右边区间的左端点

    代码2：

    class Solution {
public:
  int findLen(vector<long long>& summ, int begin_pos, int target) {
      int n = summ.size();
      int left = begin_pos, right = n - 1;
      while (left < right) {
          int mid = (left + right) / 2;
          if (summ[mid] - summ[begin_pos] >= target) {
              right = mid;
          } else {
              left = mid + 1;
          }
      }

      if (summ[left] - summ[begin_pos] >= target) {
          return left - begin_pos;
      } else {
          return -1;
      }
  }

  int minSubArrayLen(int target, vector<int>& nums) {
      int n = nums.size();
      vector<long long> summ(n + 1, 0);
      for (int i = 1; i <= n; i++) {
          summ[i] = summ[i - 1] + nums[i - 1];
      }

      int min_len = 0x3f3f3f3f;
      for (int i = 0; i < n; i++) {
          int fit_len = findLen(summ, i, target);
          if (fit_len == -1) {
              continue;
          }
          min_len = min(min_len, fit_len);
      }

      return min_len == 0x3f3f3f3f ? 0 : min_len;
  }
};