滑动窗口是处理字符串和数组问题的经典方案。
窗口滑动的思想：顾名思义，滑动窗口就是滑动的窗口，在字符串上从左往右滑动，直到串尾。滑动窗口的窗口长度是动态变化的，所以用两个指针来维护。
滑动的方向：串首—->串尾。
窗口的大小控制：何时改变i j的值。
窗口滑动实现的数据结构：高效查找，可使用hash。

  • 反射弧

最多 - 最多 = 恰好
看到最小、最大字眼，想到双指针。

1、反转字符串

  1. void reverseString(vector<char>& s) {
  2.     int left = 0;
  3.     int right = s.size() - 1;
  4.     while (left < right) {
  5.         swap(s[left], s[right]);
  6.         left++;
  7.         right--;
  8.     }
  9.     // reverse(s.begin(), s.end()); // 使用库函数
  10. }

2、反转字符串II

给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
note:
其实在遍历字符串的过程中，只要让 i += (2 k)，i 每次移动 2 k 就可以了，然后判断是否需要有反转的区间。

  1. string reverseStr(string s, int k) {
  2.     for (int i = 0; i < s.size(); i += (2 * k)) {
  3.         // 1. 每隔 2k 个字符的前 k 个字符进行反转
  4.         // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
  5.         if (i + k <= s.size()) {
  6.             reverse(s.begin() + i, s.begin() + i + k );
  7.             continue;
  8.         }
  9.         // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
  10.         reverse(s.begin() + i, s.begin() + s.size());
  11.     }
  12.     return s;
  13. }

3、904水果成篮

  1. // 904.水果成篮
  2. int totalFruit(vector<int>& tree, int K) {
  3.     int n = tree.size();
  4.     int left = 0;
  5.     int right = 0;
  7.     vector<int> mp(n, 0);
  8.     int ans = INT_MIN;
  9.     int count = 0;
  10.     while (right < n) {
  11.         if (mp[tree[right]] == 0) {
  12.             count++;
  13.         }
  14.         mp[tree[right]]++;
  15.         while (count > K) {
  16.             mp[tree[left]]--;
  17.             if (mp[tree[left]] == 0) {
  18.                 count--;
  19.             }
  20.             left++;
  21.         }
  22.         right++;
  23.         ans = max(ans, right - left); 
  24.     }
  25.     return ans;
  27. }
  29. // 795. 区间子数组个数, 注意K的取值
  30. int numSubarrayBoundedMax(vector<int>& nums, int left, int right) {
  31.     return maxK(nums, right) - maxK(nums, left - 1);
  32. }
  33. int maxK(vector<int>& nums, int k) {
  34.     int left = 0;
  35.     int right = 0;
  36.     int ans = 0;
  37.     int n = nums.size();
  38.     while (right < n) {
  39.         if (nums[right] > k) {
  40.             right++;
  41.             left = right;
  42.             continue;
  43.         }
  44.         right++;
  45.         ans += right - left;
  46.     }
  47.     return ans;        
  48. }
  50. // 992. K 个不同整数的子数组
  51. int subarraysWithKDistinct(vector<int>& nums, int k) {
  52.     return maxK(nums, k) - maxK(nums, k - 1);
  53. }
  54. int  maxK(vector<int>& nums, int k)
  55. {
  56.     vector<int> mp(nums.size() + 1, 0);
  58.     int left = 0;
  59.     int right = 0;
  60.     int count = 0; 
  61.     int res = 0;
  62.     while (right < nums.size()) {
  63.         if (mp[nums[right]] == 0) {
  64.             count++;
  65.         }
  66.         mp[nums[right]]++;
  67.         right++;
  69.         while (count > k) {
  70.             mp[nums[left]]--;
  71.             if (mp[nums[left]] == 0) {
  72.                 count--;
  73.             }
  74.             left++;
  75.         }
  76.         res += right - left; // 为什么用子数组的长度即right - left来表示增加的子数组个数呢？
  77.     }
  78.     return res;
  79. }
  80. /* 
  81. 为什么可以新用子数组的长度即right - left来表示增加的子数组个数呢？
  82. 可以借鉴动态规划的思想，举个例子就好理解了：
  83. 当满足条件的子数组从[A,B,C]增加到[A,B,C,D]时，新子数组的长度为4，同时增加的子数组为[D],[C,D],[B,C,D],[A,B,C,D]也为4。
  84. */