Leetcode-滑动窗口

Last updated on 8 months ago

1 .给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

最小的 连续子数组 : eg , [1,2,3,4,4] 连续数组 [1,2] [2,3,4]; 但是 [1,4,4] ， 下标连续

还是需要双指针，构成滑动窗口，用这窗口遍历全部数据 ，窗口结合条件是可变的，窗口大小则是我们呢的答案
滑动窗口： 窗口起点终点，和控制窗口大小的条件（本题约束窗口大小的条件是 窗口内的值总和应大于target，如果小往右扩大窗口，大了左边缩小窗口）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int minSubArrayLen(int target, vector<int> &nums) {
    int left = 0;
    int right = 0;
    int len = nums.size();
    if (nums.size() == 1) {
      return nums[0] == target ? 1 : 0;
    }
    int sum = 0;
    int ret = len;
    while (right < len) {
      sum = sum + nums[right];
      while (sum >= target) {  //窗口内的总和符合条件，则左边收缩
        ret = min(ret, right - left + 1);
        sum = sum - nums[left];
        left++;
      }
      right++;
    }
    return ret==INT_MAX?0:ret;
  }

2 . 摘水果问题 （其实套了一层皮： 窗口内只能存在两种数字，窗口最大值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int totalFruit(vector<int> &tree) {
    int res = 0;
    // 水果编号到数量的映射
    unordered_map<int, int> veg2cnt;
    int n = tree.size();
    // 窗口左边界
    int l = 0;
    // 窗口右边界
    for (int i = 0; i < n; ++i) {
      ++veg2cnt[tree[i]];
      // 一旦发现超过大小，则不断收缩窗口
      while (veg2cnt.size() > 2) {
        int currTree = tree[l];
        --veg2cnt[currTree];
        if (veg2cnt[currTree] == 0) {
          veg2cnt.erase(currTree);
        }
        ++l;
      }
      // 记录最大的窗口大小
      res = max(res, i - l + 1);
    }
    return res;
  }