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