LCP68.美观的花束——sliding_window
class Solution {
public:
const int mod = 1e9+7;
int beautifulBouquet(vector<int>& flowers, int cnt) {
int n = flowers.size();
int ret = 0;
int left = 0,right = 0;
unordered_map<int,int> count;
int option = 1;
while(right <= n){
if(option == 1){ //right指针向右边滑动，更新窗口上限
if(right == n){
option = 2;
continue ;
}
int p = ++count[flowers[right++]];
if(p > cnt){
option = 2;
}
}else{ //left指针滑动开始收缩窗口，同时不断更新答案
int span = right -1 -left;
if( right == n&& count[flowers.back()] <= cnt){ //2
span = right - left;
}
ret = (ret + span) % mod;
int p = --count[flowers[left++]];
if(p == cnt){
option = 1;
}
}
if(left == right)
break ;
}
return ret;
}
};
这道题首先由简单的枚举来过渡：比如1232，cnt=1。
我们普通的做法可以这样枚举：从左到右枚举首元素：以1开头有1、12、123，以2开头有2、23，以3开头有3、32，以2开头有2.
很明显这样枚举是可行的，但是需要O(n^2)的时间复杂度，外层for枚举开头，里层寻找终点（连续不包含cnt个重复数字的最长序列）。
比如我最开始就是这样写的：很自然的就超时了
class Solution {
public:
const int mod = 1e9+7;
int beautifulBouquet(vector<int>& flowers, int cnt) {
int n = flowers.size();
int ret = 0;
for(int i=0;i<n;i++){
int ma = 0;
unordered_map<int,int> mmp;
int j=i;
for(;j<n;j++){
int p = ++mmp[flowers[j]];
ma = max(ma,p);
if(ma > cnt){
break;
}
}
ret = (ret+(j-i))%mod;
}
return ret;
}
};
我们在枚举里层循环的时候，发现有多次重复计算，比如1开头的尾部是3，2开头的尾部还是3，那么该怎么优化呢？直接做缓存处理也是不可行的，因为无法确定后续遍历的右边界都一致。
那么如何优化呢？很快我们可以想到建立一个窗口来滑动的思想，我们的问题在于无法确认当前遍历到的头部的右边界（重复数字）是否还是前一个数确认的边界，滑动窗口可以通过哈希表记录简单的解决这一问题。
-
我们先把窗口向右扩张(
right++、++count[x])，也就是随便先找到一个右边界（这个边界内重复的数字不超过cnt个）。 -
不断的收缩窗口并更新答案(
left--,--count[x])，如果在收缩过程中count[x]被减小到正好等于cnt，那就说明之后left经过元素的有边界发生了改变，此时需要再次向右扩大窗口找到新的边界。
1和2的过程不断循环重复，直到 left 遍历并更新完了所有的元素，即 left == right 时，跳出循环。
小细节：有两种情况需要被分清楚否则会出错，1.right往后扩散发现没有重复元素（即此时没有了右边界） 2.右边界的位置就是最后一个元素的位置，即right的位置在最后一个元素的下标位置.
在我写的代码中，由于left和right始终指向还未扫描过的位置，所以上述两种情况right的值会相同都为flowers数组的大小n。但这两种情况计算答案则不同，第二种情况会少一种情况。所以有了上述题解代码的
2进行判断和处理。