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：

    1. class Solution {
    2. public:
    3.   int findLen(vector<long long>& summ, int begin_pos, int target) {
    4.       int n = summ.size();
    5.       int left = begin_pos, right = n - 1;
    6.       while (left < right) {
    7.           int mid = (left + right) / 2;
    8.           if (summ[mid] - summ[begin_pos] >= target) {
    9.               right = mid;
    10.           } else {
    11.               left = mid + 1;
    12.           }
    13.       }
    15.       if (summ[left] - summ[begin_pos] >= target) {
    16.           return left - begin_pos;
    17.       } else {
    18.           return -1;
    19.       }
    20.   }
    22.   int minSubArrayLen(int target, vector<int>& nums) {
    23.       int n = nums.size();
    24.       vector<long long> summ(n + 1, 0);
    25.       for (int i = 1; i <= n; i++) {
    26.           summ[i] = summ[i - 1] + nums[i - 1];
    27.       }
    29.       int min_len = 0x3f3f3f3f;
    30.       for (int i = 0; i < n; i++) {
    31.           int fit_len = findLen(summ, i, target);
    32.           if (fit_len == -1) {
    33.               continue;
    34.           }
    35.           min_len = min(min_len, fit_len);
    36.       }
    38.       return min_len == 0x3f3f3f3f ? 0 : min_len;
    39.   }
    40. };