题单顺序根据力扣的灵神大佬来的，思路也有借鉴灵神的，是一个自己的做题记录吧。会员题以后会补充更新，先发下不用会员的题。以后有新的相关题，我也会继续更新在这个文章中
目录
基础
1.定长子串中元音的最大数目
2.子数组最大平均数 I
3.大小为 K 且平均值大于等于阈值的子数组数目
4.半径为 k 的子数组平均值
5.得到 K 个黑块的最少涂色次数
6.几乎唯一子数组的最大和
7.长度为 K 子数组中的最大和
8.可获得的最大点数
9.爱生气的书店老板
10.拆炸弹
进阶
1.检查一个字符串是否包含所有长度为 K 的二进制子串
2.最少交换次数来组合所有的 1
3.子串的最大出现次数
4.滑动子数组的美丽值
5.重新安排会议得到最多空余时间 I
6.使二进制字符串字符交替的最少反转次数
7.字符串的排列
8.找到字符串中所有字母异位词
9.串联所有单词的子串
10.查找给定哈希值的子串
11. 统计完全子字符串
12. 子串能表示从 1 到 N 数字的二进制串
基础
1.定长子串中元音的最大数目
1456. 定长子串中元音的最大数目 - 力扣（LeetCode）
class Solution { public:int maxVowels(string s, int k) {int cnt=0;int ans=0;unordered_map<char,int>mp;for(int i=0;i<s.length();i++){cnt++;if(cnt>k){ans=max(ans,mp['a']+mp['e']+mp['i']+mp['o']+mp['u']);mp[s[i-k]]--;mp[s[i]]++;}else{mp[s[i]]++;}}ans=max(ans,mp['a']+mp['e']+mp['i']+mp['o']+mp['u']);return ans;} };
2.子数组最大平均数 I
643. 子数组最大平均数 I - 力扣（LeetCode）
class Solution { public:double findMaxAverage(vector<int>& nums, int k) {int cnt=0;int sum=0;double ans=-1e5;int n=nums.size();for(int i=0;i<n;i++){cnt++;if(cnt>k){ans=max(ans,double(sum)/k);sum-=nums[i-k];sum+=nums[i];}else{sum+=nums[i];}}ans=max(ans,double(sum)/k);return ans;} };
3.大小为 K 且平均值大于等于阈值的子数组数目
1343. 大小为 K 且平均值大于等于阈值的子数组数目 - 力扣（LeetCode）
class Solution { public:int numOfSubarrays(vector<int>& arr, int k, int threshold) {int cnt=0;int sum=0;int ans=0;int n=arr.size();for(int i=0;i<n;i++){cnt++;if(cnt>k){if(double(sum)/k >=threshold){ans++;}sum-=arr[i-k];sum+=arr[i];}else{sum+=arr[i];}}if(double(sum)/k >=threshold){ans++;}return ans;} };
4.半径为 k 的子数组平均值
2090. 半径为 k 的子数组平均值 - 力扣（LeetCode）
class Solution { public:vector<int> getAverages(vector<int>& nums, int k) {int left=0;long long sum=0;int n=nums.size();vector<int>ret(n,-1);for(int i=0;i<n;i++){if(i-2*k<0){sum+=nums[i];continue;}if(i-left+1==2*k+1){sum+=nums[i];ret[i-k]=sum/(2*k+1);left++;sum-=nums[i-2*k];}else{sum+=nums[i];}}return ret;} };
5.得到 K 个黑块的最少涂色次数
2379. 得到 K 个黑块的最少涂色次数 - 力扣（LeetCode）
class Solution { public:int minimumRecolors(string blocks, int k) {int cnt=0;int ans=INT_MAX;int n=blocks.size();for(int i=0;i<n;i++){if(i>=k){ans=min(ans,cnt);cnt-= blocks[i-k]=='W'?1:0;cnt+=blocks[i]=='W'?1:0;}else{cnt+=blocks[i]=='W'?1:0;}}ans=min(ans,cnt);return ans;} };
6.几乎唯一子数组的最大和
2841. 几乎唯一子数组的最大和 - 力扣（LeetCode）
class Solution { public:long long maxSum(vector<int>& nums, int m, int k) {unordered_map<long long, long long> mp;int n = nums.size();long long cnt = 0;long long sum = 0;long long ans = 0;for (int i = 0; i < n; i++) {if (i >= k) {if (cnt >= m) {ans = max(ans, sum);}sum -= nums[i - k];mp[nums[i - k]]--;cnt -= mp[nums[i - k]] == 0 ? 1 : 0;mp[nums[i]]++;sum+=nums[i];cnt += mp[nums[i]] == 1 ? 1 : 0;} else {sum += nums[i];mp[nums[i]]++;cnt += mp[nums[i]] == 1 ? 1 : 0;}}if (cnt >= m) {ans = max(ans, sum);}return ans;} };
7.长度为 K 子数组中的最大和
2461. 长度为 K 子数组中的最大和 - 力扣（LeetCode）
class Solution { public:long long maximumSubarraySum(vector<int>& nums, int k) {unordered_map<long long, long long> mp;int n = nums.size();int left = 0, right = -1;long long sum = 0, ans = 0;for (int i = 0; i < n; i++) {right++;if (right - left + 1 > k) {ans = max(ans, sum);mp[nums[left]]--;sum -= nums[left++];}mp[nums[right]]++;sum += nums[right];while (mp[nums[right]] > 1&&left<right) {sum -= nums[left];mp[nums[left]]--;left++;}}right++;if (right - left + 1 > k) {ans = max(ans, sum);sum -= nums[left++];}return ans;} };
8.可获得的最大点数
1423. 可获得的最大点数 - 力扣（LeetCode）
class Solution { public:int maxScore(vector<int>& cardPoints, int k) {int n=cardPoints.size();k=n-k;int sum=0,ans=INT_MAX;int ts=0;for(int i=0;i<n;i++){ts+=cardPoints[i];sum+=cardPoints[i];if(i<k-1)continue;ans=min(ans,sum);sum-=cardPoints[i-k+1];}if(k==0)return ts;return ts-ans;} };
9.爱生气的书店老板
1052. 爱生气的书店老板 - 力扣（LeetCode）
class Solution { public:int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {int sum=0;int cnt=0;int ans=0;int n=customers.size();for(int i=0;i<n;i++){if(grumpy[i]==0)cnt+=customers[i];sum+= grumpy[i]==1?customers[i]:0;if(i<minutes-1)continue;ans=max(ans,sum);sum-= grumpy[i-minutes+1]==1?customers[i-minutes+1]:0;}return cnt+ans;} };
10.拆炸弹
1652. 拆炸弹 - 力扣（LeetCode）
class Solution { public:vector<int> decrypt(vector<int>& code, int k) {int sum=0,n=code.size();vector<int>arr(n,0);if(k==0)return arr;int r= k>0?k:n-1;k=abs(k);sum=reduce(code.begin()+r-k+1,code.begin()+r+1);for(int i=0;i<n;i++){r++;arr[i]=sum;sum+=code[(r)%n]-code[(r-k)%n];}return arr;} };
进阶
1.检查一个字符串是否包含所有长度为 K 的二进制子串
1461. 检查一个字符串是否包含所有长度为 K 的二进制子串 - 力扣（LeetCode）
class Solution { public:bool hasAllCodes(string s, int k) {long long cpy=pow(2,k);unordered_map<string,long long>mp;string cmp="";long long sum=0;long long n=s.size();for(int i=0;i<n;i++){cmp+=s[i];if(i<k-1)continue;if(++mp[cmp.substr(i-k+1,k)]==1)sum++;}if(sum==cpy)return true;else return false;} };
2.最少交换次数来组合所有的 1
2134. 最少交换次数来组合所有的 1 II - 力扣（LeetCode）
class Solution { public:int minSwaps(vector<int>& nums) {int cpy = reduce(nums.begin(), nums.end());int sum = 0, n = nums.size();int ncpy = n - cpy;int ans1 = INT_MAX, ans2 = INT_MAX;if (cpy != 0) {for (int i = 0; i < n; i++) {sum += nums[i];if (i < cpy - 1)continue;ans1 = min(ans1, cpy - sum);sum -= nums[i - cpy + 1];}}sum = 0;if (ncpy != 0) {for (int i = 0; i < n; i++) {sum += nums[i];if (i < ncpy - 1)continue;ans2 = min(ans2, sum);sum -= nums[i - ncpy + 1];}}return min(ans1, ans2);} };
3.子串的最大出现次数
1297. 子串的最大出现次数 - 力扣（LeetCode）
class Solution { public:int maxFreq(string s, int maxLetters, int minSize, int maxSize) {int ans=0,cnt=0,n=s.size();unordered_map<string,int>mp;unordered_map<char,long long>pp;string tmp;for(int i=0;i<n;i++){tmp+=s[i];if(++pp[s[i]]==1)cnt++;if(i<minSize-1)continue;cout<<tmp<<" "<<cnt;if(cnt<=maxLetters){ans=max(ans,++mp[tmp]);}cnt-=--pp[s[i-minSize+1]]==0?1:0;tmp.erase(tmp.begin());}return ans;} };这个要注意，核心就是不要被maxsize给误导了，因为在[minsize+1,maxsize]这个长度区间，子串的重复次数，肯定小于等于长度minsize的子串重复次数，比如'abcabcdfabcabc',在这里，abcabc这个子串重复了2次，abc重复了4次。
4.滑动子数组的美丽值
2653. 滑动子数组的美丽值 - 力扣（LeetCode）
class Solution { public:vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {map<long long,long long>mp;int n=nums.size();vector<int>ans(n-k+1,0);for(int i=0;i<n;i++){mp[nums[i]]++;if(i<k-1)continue;int cnt=0;for(auto &c:mp){cnt+=c.second;if(cnt>=x){ans[i-k+1]=c.first<0?c.first:0;break;}}mp[nums[i-k+1]]--;}return ans;} };但这题可以直接开数组，不用容器，容器遍历复杂度有点高。
class Solution { public:vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {const int N=1e5;int mp[2*N+1];memset(mp,0,sizeof(mp));int n=nums.size();vector<int>ans(n-k+1,0);for(int i=0;i<n;i++){mp[nums[i]+51]++;if(i<k-1)continue;int cnt=0;for(int j=0;j<N+52;j++){cnt+=mp[j];if(cnt>=x){ans[i-k+1]=j-51<0?j-51:0;break;}}mp[nums[i-k+1]+51]--;}return ans;} };暴力搜索，正解应该懒删除堆法。
5.重新安排会议得到最多空余时间 I
3439. 重新安排会议得到最多空余时间 I - 力扣（LeetCode）
class Solution { public:int get(int i,int eventTime,vector<int>& startTime, vector<int>& endTime){int n=startTime.size();if(i==0){return startTime[0]-0;}else if(i==n){return eventTime-endTime[n-1];}return startTime[i]-endTime[i-1];}int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {int sum=0,n=startTime.size();int ans=0;for(int i=0;i<=n;i++){sum+=get(i,eventTime,startTime,endTime);if(i<k)continue;ans=max(ans,sum);sum-=get(i-k,eventTime,startTime,endTime);}return ans;} };思路一下子想不出来，看了灵神的思路。一开始想着那边lambda函数没必要，后面写着，才知道，不用函数压根不好写条件。但lambda看着还是比较抽象的，我写了普通的函数。但lambda确实方便。
6.使二进制字符串字符交替的最少反转次数
1888. 使二进制字符串字符交替的最少反转次数 - 力扣（LeetCode）
空间未优化
class Solution { public:int minFlips(string s) {int sum=0,n=s.size(),ans=INT_MAX;char prev='1';s+=s;for(int i=0;i<2*n;i++){sum+=s[i]==prev?1:0;prev=prev=='1'?'0':'1';if(i<n-1)continue;ans=min({ans,sum,n-sum});char par;if(n%2!=0){par=prev;}else{par=prev=='1'?'0':'1';}sum-=(s[i-n+1]==par?0:1);}return ans;} };时间复杂度:O(N),空间复杂度:O(N)
精选的题解讲的太简略了，灵神的那个看着有点复杂。
我看了好多篇题解，发现这样写是挺好的。
核心：通过双倍字符串，结合滑动窗口，可以遍历所有可能得组合字符串。具体的可以看精选的题解的图解部分。
prev是位置i正确的字符。
需要明白的点：检测10串得到的次数，等于s长度-检查01串得到的次数 的次数。
因此开局选择其中一个作为prev即可。以下以01串开始。
i与prev比较即可，相同就增加次数。
如果n为奇数，以i-n+1为开始的滑动窗口，可以复原得到，i-n+1位置的正确字符应该是跟当前i位置的正确字符相等。
而如果n偶数数，则相反即可，比如0101。
优化下空间。
class Solution { public:int minFlips(string s) {int sum=0,n=s.size(),ans=INT_MAX;char prev='1';//s+=s;for(int i=0;i<2*n;i++){sum+=s[i%n]==prev?1:0;prev=prev=='1'?'0':'1';if(i<n-1)continue;ans=min({ans,sum,n-sum});char par;if(n%2!=0){par=prev;}else{par=prev=='1'?'0':'1';}sum-=(s[(i-n+1)%n]==par?0:1);}return ans;} };时间复杂度:O(N),空间复杂度:O(1)
更优秀的答案，遍历长度达不到2*n，但我个人能力有限，基于我目前的代码，还不知道该怎么优化。
有兴趣的可以自己试试
7.字符串的排列
567. 字符串的排列 - 力扣（LeetCode）
class Solution { public:bool checkInclusion(string s1, string s2) {unordered_map<char, int> pare;int cnt = 0;int n = s2.size(), k = s1.size();for (auto& x : s1) {pare[x]++;}unordered_map<char, int> mp;for (int i = 0; i < n; i++) {mp[s2[i]]++;if (mp[s2[i]] <= pare[s2[i]])cnt++;if (i < k - 1)continue;if (cnt == k)return true;if (mp[s2[i - k + 1]] <= pare[s2[i - k + 1]])cnt--;mp[s2[i - k + 1]]--;}return false;} };
8.找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
class Solution { public:int pare[26],mp[26];vector<int> findAnagrams(string s, string p) {for(auto &x:p)pare[x-'a']++;int n=s.size(),k=p.size();int cnt=0;vector<int>ret;for(int i=0;i<n;i++){if(++mp[s[i]-'a']<=pare[s[i]-'a'])cnt++;if(i<k-1)continue;if(cnt==k)ret.push_back(i-k+1);if(mp[s[i-k+1]-'a']--<=pare[s[i-k+1]-'a'])cnt--;}return ret;} };一开始想着用unordered_map的，后面发现，只有小写字母，那开个数组就够了。
9.串联所有单词的子串
30. 串联所有单词的子串 - 力扣（LeetCode）
class Solution { public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string, int> pare, mp;for (auto& x : words) {pare[x]++;}auto check = [&]() {for (auto& x : pare) {if (!mp.count(x.first))return false;if (mp[x.first] != x.second)return false;}return true;};int n = s.size(), k = words.size(), p = words[0].size();vector<int> ret;for (int t = 0; t < p; t++) {mp.clear();for (int i = t+p-1; i < n; i+=p) {string tmp=s.substr(i-p+1,p);mp[tmp]++;if(i<t+p*k-1)continue;if(check())ret.push_back(i-p*k+1);string cp=s.substr(i-p*k+1,p);mp[cp]--;}}return ret;} };
10.查找给定哈希值的子串
2156. 查找给定哈希值的子串 - 力扣（LeetCode）
class Solution { public:string subStrHash(string s, int power, int modulo, int k, int hashValue) {int n = s.size();long long hash = 0, pk = 1;long long ans=0;for (int i = n - 1; i >= 0; i--) {if (i >= n - k) {hash = (hash * power + (s[i] - 'a' + 1))%modulo;pk *= power;pk%=modulo;if(i==n-k&&hash==hashValue)ans=i;} else{hash=(hash*power+(s[i]-'a'+1)-pk*(s[i+k]-'a'+1)%modulo+modulo)%modulo;if(hash==hashValue)ans=i;}}return s.substr(ans,k);} };这题重点不是滑动窗口，核心是秦九韶算法对多项式计算的优化，配合从右往左的滑动窗口完成本题。思路是看灵神的。
11. 统计完全子字符串
2953. 统计完全子字符串 - 力扣（LeetCode）
class Solution { public:int cnt[26];int func(const string&s,int k){int n=s.size();int res=0;auto check=[&](){for(auto &x:cnt){if(x>0&&x!=k)return;}res++;};for(int i=1;i<=26&&i*k<=n;i++){memset(cnt,0,sizeof (cnt));for(int j=0;j<n;j++){cnt[s[j]-'a']++;if(j<i*k-1)continue;check();cnt[s[j-i*k+1]-'a']--;}}return res;}int countCompleteSubstrings(string word, int k) {//分组循坏，通过第二个条件，先划分多个区间段，每个区间串计算其满足条件1的子串数量//最后把所有区间段的结果累加起来，就是最终答案。//分组循坏int n=word.size();int ans=0;for(int i=0;i<n;i++){int start=i;for(i++;i<n;i++){if(abs(int(word[i])-int(word[i-1]))>2)break;}i--;ans+=func(word.substr(start,i-start+1),k);}return ans;} };这份是O(26*26*n)复杂度，思路是灵神那边提供的，我只能说我自己看懂了吧。
下面是时间复杂度继续优化的结果。
class Solution { public:int cnt[26];static const int N=1e5+1;int pt[N];int func(const string&s,int k){int n=s.size();int res=0;for(int i=1;i<=26&&i*k<=n;i++){memset(pt,0,sizeof pt);memset(cnt,0,sizeof (cnt));for(int j=0;j<n;j++){pt[cnt[s[j]-'a']]--;cnt[s[j]-'a']++;pt[cnt[s[j]-'a']]++;if(j<i*k-1)continue;if(pt[k]==i)res++;pt[cnt[s[j-i*k+1]-'a']]--;cnt[s[j-i*k+1]-'a']--;pt[cnt[s[j-i*k+1]-'a']]++;}}return res;}int countCompleteSubstrings(string word, int k) {//分组循坏，通过第二个条件，先划分多个区间段，每个区间串计算其满足条件1的子串数量//最后把所有区间段的结果累加起来，就是最终答案。//分组循坏int n=word.size();int ans=0;for(int i=0;i<n;i++){int start=i;for(i++;i<n;i++){if(abs(int(word[i])-int(word[i-1]))>2)break;}i--;ans+=func(word.substr(start,i-start+1),k);}return ans;} };复杂度优化到了O(26*n);
但要浪费一个O(n)的空间。用哈希的话速度太慢了，哈希查询很快，但是清空或者创建，比较费时间。
12. 子串能表示从 1 到 N 数字的二进制串
1016. 子串能表示从 1 到 N 数字的二进制串 - 力扣（LeetCode）
暴力做法
class Solution { public:bool queryString(string s, int n) {for(int i=1;i<=n;i++){auto tmp=bitset<32>(i).to_string();//这个是bitset的初始化用法//这里是创建了个匿名的bitset对象，这个对象可以存32位数字//将i转换成二进制数存入这个匿名对象，然后再利用to_string()//把这个对象存的二进制数以字符串的形式展现出来。int index=tmp.find('1');if(s.find(tmp.substr(index))==-1)return false;}return true;} };这个做法，我一开始下意思是不想做的，我刚开始下意思想的是下面的一个版本，直到看见灵神的题解，才发现暴力竟然也能过。复杂度的解析我这里就不赘述了，灵神讲的很详细了。时间复杂度：O(min(m,n)⋅mlogmin(m,n))。空间复杂度：O(logn)
-------------------------------------------------------------------------------------------
接下来是我一开始想的思路，不过我一开始就只想到了要把s的所有子串转换成数字存起来，
但是当时觉得会超时，因为每次都要以i为起点，往后找子串，但是看了灵神的分析，每次的起点只需要在1的位置即可，并且当转换的数字大于n，就可以break掉，每个起点只需要遍历logn次即可。
class Solution { public:bool queryString(string s, int n) {int m=s.size();unordered_set<int>mp;for(int i=0;i<m;i++){if(s[i]=='0')continue;int sum=s[i]-'0';mp.insert(sum);for(int j=i+1;j<m&&sum<=n;j++){sum=(sum<<1)|(s[j]-'0');//看灵神学会的，很妙if(sum<=n)mp.insert(sum);}}return mp.size()==n;} };我尝试过代码是否可以写得更加简洁，但发现改不了。只能换一下，代码量差不多。
--------------------------------------------------------------
灵神还有一份解法，这个解法，这个思路是主要是基于灵神对算法1复杂度解析之后得出的结果。不推荐写，虽然复杂度很低，是线性的复杂度，O(m)，但思考过程有点点非人了。
下面是我仿照灵神写的，主要是加了些解释性的话。思路分析可以看灵神的。
class Solution { public:bool queryString(string s, int n) {if(n==1)return s.find("1") !=-1;int m=s.size();int k=31-__builtin_clz(n);//这个函数用于计算一个整数的二进制表示中，//从最高位开始连续的0的个数。这样的结果就是n的有效二进制长度-1，省去无意义的0if(m<max(n-(1<<k)+k+1,(1<<(k-1))+k-1))return false;//这个是分析得到的一个结论，具体可看灵神的分析//下面是对长为k的在[left,right]内的二进制数，判断这些数s是否都有auto check=[&](int k,int left,int right)->bool {if(left>right)return true;unordered_set<int>seen;int mask=(1<<(k-1))-1;//这个是用来抹除最高bit位的。//也就是k-2位全为1的二进制数int x=stoi(s.substr(0,k-1),nullptr,2);//把前k-1个二进制数转换成10进制//开始进行滑动窗口，遍历子串for(int i=k-1;i<m;i++){x=((x&mask)<<1)|(s[i]-'0');//x&mask,就是用k-1个二进制数与k-2个1进行与操作，从而去掉最高位//后面的操作，就是滑动窗口的入操作，这个很好懂，左移1位，再与一下if(left<=x&&x<=right){seen.insert(x);}}return seen.size()==right-left+1;};return check(k,n/2+1,(1<<k)-1)&&check(k+1,1<<k,n);//这个也是分析的结论，我虽然看懂了，但是讲还是有点讲不明白的，有兴趣看灵神的分析。} };
