哈希表+前缀和+滑动窗口高效查找——蓝桥杯例题

 题目一【子串分值和】——前缀和

题目分析：本题目给定任意长度为n的字符串，要求算出该字符串的所有子串的f(子串)的值。给定f(子串)的值为子串中出现的不同字母个数，例如f(abc)=3,f(aaa)=1。一般比较容易想到的思路就是遍历出所有的子串，然后对依次算出f(子串)的值即可。如果在时间不允许的情况下，优先考虑用暴力解法，但是这题如果用暴力解法对于给定的强测试数据组必定会超时，因为n的值为10的5次方，那么非空子串数量就达到n！ 这是一个非常庞大的数据了。不过我们可以利用这种暴力解法结合哈希表来优化一下代码，这种思路也比较容易理解。

int main()
{//暴力解法unordered_map <char, char>  hash_letter;//创建一个字符类型的哈希表string s;int sum=0;cin >> s;for (int i = 0; i < s.size(); i++){if (hash_letter.find(s[i]) == hash_letter.end()){hash_letter[s[i]] = s[i];}//如果表中没有就存入for (int j = i ; j < s.size(); j++)//取子串{if (hash_letter.find(s[j]) == hash_letter.end())//如果表中没有就存入hash_letter[s[j]] = s[j];//将字符存入哈希表中// if (i==0&& j ==(s.size()-1))break;//字符串本身sum+=hash_letter.size();}hash_letter.clear();//遍历完记得清零哈希表}cout << sum;return 0;
}

代码分析：实际上就是遍历出所有子串，这里的子串如何遍历呢？假设长度为n的字符串。实际上就是从第一个字母开始，一直遍历到最后一个字母，每遍历到下一个字母时都是一个新的子串。这样完成第一遍遍历（子串数量为n）。然后下一次再从第二个字母开始，一直遍历到第n个字母，这样完成第二遍遍历（子串数量为n-1）......这样一直循环，直到完成第n遍遍历为止。所以子串数量为n*(n-1)*......*1。在遍历子串的过程中同时计算f(子串)，我们采用哈希表来存储这些字母，只有当哈希表不存在这个字母时，我们才存储这个字母，否则不予处理。不过在每次遍历完以第i个字母为首的字符串后，记得把哈希表清零，这样才方便下一次遍历以第i+1为首的字符串。用哈希表可以快速实现查取功能，我们的f(子串)的值就是哈希表的大小值。因为哈希表中的字母都是不一样的。我们每次遍历时把hash.size()的值累加即可。虽然利用了哈希表的高效查取，但是由于子串数量过于庞大，仍然还会超时。这样子做可以通过60%的数据。

那么我们思考：有没有一种解决办法，可以避开遍历子串的数量呢？

答案是有，我们不依次遍历子串了，我们只用遍历子串的每个字母即可，也就是遍历长度是n。

#include <bits/stdc++.h>
//优化代码
using namespace std;
int main()
{string s;char letter;long long int sum=0,left=0,st_left=0;
cin >> s;for (int i = 0; i < s.size(); i++)//遍历每个字母对字符串的贡献{letter = s[i];for (int j = i + 1; j < s.size(); j++)//找下一次出现的位置{if (letter == s[j]) {left = j;st_left = 1;break;}}if (!st_left) left = s.size();if (st_left == 1) st_left = 0;sum += (i+1) * (left-i);}cout << sum;return 0;
}

代码思路：我们可以使用构造子串的办法，不直接计算f(子串)的值，而是计算满足条件的子串有多少，换一种理解方式，就是这个字母对多少子串有贡献。如何计算满足条件的子串有多少呢？这里我们假设遍历到了第i个字母，那么这个字母对多少子串是有贡献的呢？这里就要更具f(子串)的值来进一步分析了。因为f是不同字母的数量，所以我们关注的是相同的字母的位置。我们要构造子串的数量，就要确定子串的端点范围。也就是左端点和右端点。只要我们确定了端点，就可以计算出子串的数量了。这里先确定左端点的范围是多少。因为我们是要判断这第i个字母是否有贡献，其实子串的左端点也就不那么重要了，因为这个字母的贡献值要么为0，要么为1。我们以第i个字母为起点，对起点左侧的字母我们不再关心了，因为不管左侧的字符串是否出现相同的字母，反正该字母的贡献值已经为1了(因为这个字母已经出现了)，现在我要关心的是这个字母的贡献何时失效。也就是看右端点了。从第i个位置往后看，当没有再次出现相同字母时，这个字母对这些子串都是有贡献的，但是如果再次出现了这个字母，那么这第i个字母就失效了，因为已经出现了第二个相同的字母，但是f的值仍然为1。所以我们要关心的是右端点的值，而这个值next就等于这个字母下一次出现的位置-1.所以能构造出来的子串数量num=i*(next-1-i)。

这里如何理解呢？因为我们构造出来的子串必须要包含当前字母，所以我们可以把当前字母想象为一个节点，在此节点党的左侧有i种可能，右侧有（next-1-i）种可能，所以要算通过此节点一共有多少条路径，那么就是左侧的可能数*右侧的可能数。这样子理解起来就比较方便了。

注意：因为字符串下标是以0开始的，我们在计算结果的时候人为加上1就可以了，如果不加1，计算结果就会出错。

这里还需要注意，当我们找到了下一个相同的字母时，应该将标志位置1，循环结束后，如果标志位没有被置1，说明没有找到相同的字母，直接把右端点长度设置为字符串的长度即可。还需注意，记得把标志位清零，不然会影响下一个字母的判断。

题目二【子串分值】——前缀和

题目分析：这题与上一题的思路大致一致，我们要避开遍历所有的子串，而是计算满足条件的子串有多少，这里的满足条件就是指当前字母是否对包含这个字母的子串有效。是否有效如何判断呢？我们看题目要求，题目的f(子串)的值是只出现一次的字母的数量，所以我们关心的还是相同字母。

using namespace std;
int main()
{int left = 0, right = 0,sum=0,st_left=0,st_right=0;string key;char letter=' ';cin >> key;for (int i = 0; i < key.size(); i++)//遍历该字符串中的每一个字母{letter = key[i];for (int j = i+1; j < key.size(); j++)//找到下一个相同字母的位置{if (key[j] == letter){right = j;st_right = 1;//标志位break;}}if (!st_right) right = key.size();//找不到就计为长度值else st_right = 0;//清除标志位for (int j = i-1; j >= 0; j--)//找到上一个相同字母的位置{if (key[j] == letter) {left = j;st_left = 1;break;}}if (!st_left) left = -1;//找不到就计为-1，说明是第一次出现else st_left = 0;//清除标志位sum += (i - left) * (right - i);//计算能构造出来多少子串//   cout << sum << endl;}cout << sum;return 0;
}

代码思路：上面解释到我们关心的是相同字母，那么我们大胆假设，假设遍历到了第i个字母时，到底有没有一种办法可以构造出一个能满足条件的子串呢？这里的条件就是第i个字母只出现一次 。因此我们就不仅仅只关心这个字母下一次出现的位置（next）了，还要关心这个字母上一次出现的位置(front)。这样子串只要满足左端点位于(i-front,i),右端点位于(i,next-1)即可。那么子串数量就是(i-front)*(next-i)，累计加即可。

注意：这里在找到了下一个字母或者上一个字母时记得把标志位置1，如果遍历完之后仍然没找到相同的字母，那么就把next赋值为string.size()，front赋值为-1即可。每次遍历完后把标志位清零，放置干扰遍历下一个字母。

 题目三【两数之和】——哈希表

题目分析：给定一组数组和sum值，判断在该数组中是否存在两个数相加和为sum。 

这题思路比较容易，就是遍历计算补数(sum-arr[i])，利用哈希表来实现查找功能即可。

#include <bits/stdc++.h>
using namespace std;
int findTwoSum(vector<int> x, int n, int sum) {unordered_map <int, int> hash;//创建一个键为vector类型，键值为int类型的哈希表int com = 0;for (int i = 0; i < n; i++) {//将数据存储到哈希表中hash[x[i]] = i;}for (int i = 0; i < n; i++) {com =sum-x[i];//计算补值if (hash.find(com) != hash.end()) //查找成功{return 1;}else continue;//否则继续查找}return -1;}
int main()
{int n, sum;   cin >> n; vector<int> v(n);for (int i = 0; i < n; i++){cin >>v[i];//输入键值 1 2 2 4 5}cin >> sum;cout << findTwoSum(v, n, sum);return 0;
}

代码分析：我们利用动态数组vector来存入数组，然后把数组中的元素遍历存入到哈希表的键中去(注意是键，而不是键值。因为哈希表查找的是键) 。然后循环计算补数，判断该哈希表中是否存在对应的补数即可。

题目四【美丽串】双指针.滑动窗口 

题目分析：这里又涉及到关于子串的问题了，题目要求求出重复字母数量不超过k的最长子串的长度。一般思路就是设置一个数组，来记录下不同字符的数量分别是多少，因为这里字符最多也就是26个，我们可利用字符-‘a’的值来代替不同的字符。这样方便我们每次都将对应的字符存入cnt数组中计数。那么只要cnt数组中有一个字符数量到达了k值，我们就计算长度，把结果取最小值即可。

#include <bits/stdc++.h>
using namespace std;
int main()
{string s;int k,cnt[26]={0};long long n,l=0,r=0,res=0;cin>>s>>k;n=s.size();while(l<n){while(r<n){if(cnt[s[r]-'a']==k) break;cnt[s[r]-'a']++;r++;}res=max(res,(r-l));cnt[s[l]-'a']--;l++;}cout<<res;// 请在此输入您的代码return 0;
}

代码分析：不过这里我们需要思考，有没有什么办法可以简化遍历子串的复杂度呢？这里我们就采取双指针的办法，建立左指针变量和右指针分别指向子串的左端点和右端点。左端点先保持不变，右端点依次往后递增，当右端点移动到满足条件时便计算长度(右端点-左端点+1)，因为这里的右端点实际上指向的是满足条件的子串的右端点的后一位(退出第二个循环时r的值实际上已经不符合条件了)， 所以这里不需要+1，因为r的值本身已经是满足条件的右端点的值+1了。当右指针不满足条件时，左指针才会++，继续判断下一个子串。这里有一个特点：r指针只会往后移动，不会再往前移动了。所以利用这样的双指针来实现遍历子串的方法可以减少时间复杂度。

题目五【最短子串】双指针.滑动窗口 

 题目分析：题目要求计算出包含序列中所有数字的最短子串的长度。那么实际上和上一个题目是一样的，在逻辑上有一些细节不一样。但是本质上还是优化对子串的遍历。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(x) (x).begin(),(x).end()int st_cnt[9]={0};
void get_dis(vector<int> x){//计算有多少不同的数字 for(int i=0;i<x.size();i++){st_cnt[x[i]]++;}
} 
bool include(int x,int y,vector<int> z){	int cnt[9]={0};		for(int j=x;j<=y;j++)//取出该序列所有数字 {cnt[z[j]]++;} for(int i=0;i<=9;i++)//判断是否不存在某个数字 {if(st_cnt[i]!=0){//对现有的不同字母进行判断 if(cnt[i]==0)  return false;		 					    }} 	return true;
} 
int main(){ios::sync_with_stdio(false),cin.tie(0);// cin>>s;vector<int> s;cin>>s;get_dis(s);//存入不同的数字 int n=s.size();int l=0,r=0;ll res=0;while(l<n){while(r<n){ if(!include(l,r,s)) {r+=1;continue;}else {res=r-l+1; break;}//满足条件就退出计算最小长度 }if(r==n){if(!include(l,r-1,s)) break;  //剪枝    }  if(include(l,r,s))res=min(res,(ll)(r-l+1)); l++;}cout<<res;return 0;
}

代码分析：简化对子串的遍历我们仍然采取双指针的办法。这里我们着重分析一下细节问题。

首先就是要考虑记录下这个序列中有多少不同的数字，我们用一个数组来记录。这个数组中记录的是序列中0~9这些数字的个数。我们用get_dis(s)这个函数就可以实现了。在接下来就是对子序列的判断了，我们用一个bool型的函数include(int x,int y,vector<int> z)来实现。这里的x代表左指针，r代表右指针，z代表序列本身。我们在include中要实现获取以左指针为左端点，右指针为右端点的子序列里的所有数字的数量。下一步利用st_cnt数组来判断是否含有所有的数字了。当没有包含所有的数字时，我们返回false，反之则返回true。在遍历子序列的时候，我们利用include函数来决定是否要继续移动右指针。当不满足条件时，我们继续移动，当满足条件时，我们停止移动，并计算出此时子序列的长度。这里有一个可以实现剪枝的判断：当右端点已经到达了最后时，如果此时的子序列还是不满足条件，那么左端点也没有必要继续移动了，因为再往后移动也没有新的数字出现了，此时直接退出循环即可。这里计算长度的条件是include返回为true。所以在计算长度是记得要加上判断，因为这里退出第二个循环的条件不只有include返回为真，还有r=s.size()。所以需要加上判断。最后结果取最小值即可。