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 进行判断和处理。