C++ 滑动窗口、二分查找

滑动窗口算法第一步初始化游标，初始化游标i和j，其中i为0，j为-1，代表一开始是一个空窗口。

第二步是控制右游标，固定左游标i，当右游标j小于n-1的时候，扩大右游标j的值，也就是让j变成j+1。

第三步是控制左游标，根据题目条件进行判定，如果发现条件不满足，则扩大左游标i的值，也就是让i变成i+1。

第四步是记录最优解，在迭代窗口【i，j】的过程中，记录最优区间或者满足条件的区间方案数，并且最终返回答案即可。

代码分析，第一步框架分析

function slideWindows(n, arr,...)

  i = 0, j = -1

  while(j < n)

    j += 1;

    while cond(n, arr, i, j,...)

      i += 1

      ans = calc(n, arr, i, j)

return ans

另一版，对应上述的文字描述的

function slideWindows(n, arr, k)

  i = 0, j = -1, sum = 0, ans = 0

  while(j < n)

    j += 1;

    sum += arr[j]

    while sum >= k

      ans += n - j

      sum -= arr[j]

      i += 1

return ans

对应代码，蓝桥云课 挑选子串 代码见下

#include <iostream>
using namespace std;

int sliceWindows(int n, int k, int *a){
  int i=0, j=-1;
  int sum = 0;
  int ans = 0;
  while( j++ < n-1){
    sum += a[j];
    while(sum >= k){
      ans += n - j; 
      sum -= a[i];
      i++;
    }
  }
  return ans;
}

int main()
{
  int n, m, k;
  int a[2001];
  cin >> n >> m >> k;
  for(int i=0; i<n; ++i){
    cin >> a[i];
    a[i] = (a[i] >= m ? 1:0);

  }
  int ans = sliceWindows(n, k, a);
  cout << ans << endl;


  // 请在此输入您的代码
  return 0;
}

代码练习，对应蓝桥云课 最长子串 代码见下

#include <iostream>
#include <string>
using namespace std;

int sliceWindow(int n, int k, const string& a){
  int i=0, j=-1;
  int count[256] = {0};
  int ret = 0;
  while(j++ < n-1){
    count[a[j]]++;
    while(count[a[j]] > k){
      count[a[i]]--;
      i++;
    }
    int x = j - i + 1;
    ret = max(ret, x);
  }
  return ret;
}
int main()
{
  int n, k;
  string s;
  cin >> s;
  cin >> k;
  int ans = sliceWindow(s.size(), k, s);
  cout << ans << endl;
  // 请在此输入您的代码
  return 0;
}

代码，对应蓝桥云课 全部都有的子序列 代码见下

#include <iostream>
#include <cstring>
using namespace std;

int sliceWindow(int n, int *a){
  int i=0, j=-1;
  int count[1001] = {0};
  int need = 0, tot = 0;
  int ret = n;
  for(int i=0; i<n; ++i){
    count[a[i]]++;
    if(count[a[i]] == 1){
      need++;
    }
  }

  memset(count, 0, sizeof(count));

  while(j < n-1){
    j++;
    count[a[j]]++;
    if(count[a[j]] == 1){
      tot++;
    }
    while(tot == need){
      ret = min(ret, j - i + 1);
      count[a[i]]--;
      if(count[a[i]] == 0){
        tot--;
      }
      i++;
    }
  }
  return ret;
  
}

int a[100001];
int main()
{
  int n;
  cin >> n;
  for(int i=0; i<n; ++i){
    cin >> a[i];
  }
  int ans = sliceWindow(n, a);
  printf("%d\n", ans);
  // 请在此输入您的代码
  return 0;
}

二分查找很常用，直接看以下代码分析

二分查找第一步：函数定义

function findMinGreenIndex(array, len, target)

  l = -1, r = len

  while l + 1 < r

    mid = (l + r)/2

    if isGreen(array, mid, target)

       r = mid

    else

       l = mid

return r

第二步，判绿函数

function isGreen(array, mid, target)

  return array[mid] >= target

关于二分查找的相关细节

第一个细节：二分查找的过程是不断向着目标值的边界范围值靠近

第二个细节：迭代结束的条件是区间范围值为2

第三个细节：初始值，分别是 -1 和 n（避免边界值存在问题）

第四个细节：由于中点的位置是需要访问数组去获得值的，所以必须始终满足在[0, n) 的范围内

代码练习，对应力扣，搜索插入位置，代码见下

class Solution {
    bool isGreen(vector<int>& nums, int mid, int t){
        return nums[mid] >= t;
    }
    int bSearch(vector<int>& nums, int t){
        int l = -1;
        int r = nums.size();
        while(l + 1 < r){
            int mid = (l + r)/2;
            if (isGreen(nums, mid, t)){
                r = mid;
            }else{
                l = mid;
            }

        }
        return r;
    }
public:
    int searchInsert(vector<int>& nums, int target) {
        return bSearch(nums, target);
    }
};

代码练习 对应力扣 在排序数组中查找第一个和最后一个位置 代码见下

class Solution {
    bool isGreen(vector<int>& nums, int mid, int t){
        return nums[mid] >= t;
    }
    int bSearch(vector<int>& nums, int t){
        int l = -1;
        int r = nums.size();
        while(l + 1 < r){
            int mid = (l + r)/2;
            if (isGreen(nums, mid, t)){
                r = mid;
            }else{
                l = mid;
            }

        }
        return r;
    }
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int idx = bSearch(nums, target);
        if(idx == nums.size()){
            return {-1, -1};
        }
        if(nums[idx] != target){
            return {-1, -1};
        }
        vector<int> ret;
        ret.push_back(idx);
        int idx1 = bSearch(nums, target+1);
        ret.push_back(idx1 - 1);
        return ret;

    }
};