LC209.长度最小的子数组

原题链接

思路1：滑动窗口

• 此题可以当做滑动窗口的模板题，非常典型。

代码1

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0;
        int n = nums.size();
        int cur_sum = 0;
        int min_len = 0x3f3f3f3f;
        while (right < n) {
            cur_sum += nums[right];
            while (cur_sum >= target) {
                cur_sum -= nums[left];
                min_len = min(min_len, right - left + 1);
                left += 1;
            }

            right += 1;
        }

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

思路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;
    }
};