题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个数组和一个整数，找出数组中总和大于该整数的子数组中的最小长度。

思路分享

  • 不定长滑动窗口(% post_link 3090每个字符最多出现两次的最长字符串 %)的简单变式，不过以往的滑动窗口是为了求最长值，这里是求最短值。

  • 所以陆爻齐有个想法，以前都是主循环窗口右侧，不满足条件就让窗口左侧右滑，那么就反过来，主循环窗口左侧滑动，不满足这个条件就让窗口右侧右滑，这就是下面的代码的意思。

代码解答（强烈建议自行解答后再看）

  • 陆爻齐的参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ans = INT_MAX;
        int right = 0;
        int sum = 0;
        for (int left = 0; left < n; left++) {
            while (sum < target && right < n) {
                sum += nums[right++];
            }
            if (sum >= target && right <= n) {
                //cout << sum << " " << left << " " << right << endl;
                ans = min(ans, right-left);
            }
            sum -= nums[left];
        }
        return ans==INT_MAX ? 0 : ans;
    }
};