题目描述
blablabla
第一个条件就是让辅音和原音字母数量相同
可以用前缀和转换成,从数组挑两个点
sum1[i]-sum1[j]=sum2[i]-sum2[j]相同
然后合并相同下标即可
sum1[i]-sum2[i]=sum1[j]-sum2[j]
所以记录sum1[i]-sum2[i]即可
拿个哈希表存着即可,
第二个条件
已知sum1[i],sum2[i]
使得(sum1[i]-x)*(sum1[i]-x)%k==0
直接枚举x就行
只要一个sum1[i]即可,因为第一个条件原音和辅音相同
因为k很小考虑枚举即可
再记录sum1[i]%k的余数即可
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
using node=tuple<int,int,int>;
class Solution {
public:
long long beautifulSubstrings(string s, int k) {
int n=s.size();
s="?"+s;
long long res=0;
unordered_map<int,map<int,int>> mp;
mp[0][0]++;
int s1=0,s2=0;
for(int i=1;i<=n;i++)
{
if(s[i]!='a'&&s[i]!='e'&&s[i]!='i'&&s[i]!='o'&&s[i]!='u'){
s1++;
}
else s2++;
for(int j=0;j<k;j++){
int x=((s1-j)*(s1-j)%k+k)%k;
if(x==0&&mp[s1-s2].count(j))
res+=mp[s1-s2][j];
}
mp[s1-s2][s1%k]++;
}
return res;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla