字节跳动面试--三面算法题复盘
题目描述：
查找字符串中给定的连续不重复序列
给定如下不重复序列和一个字符串，请返回不重复序列连续出现在字符串中第一个字母的位置。
例如
给定不重复序列[a，b，c，d]
字符串adcebadcb
则返回4
解题思路：
个人以为，此题的解题关键在于如何去判断一个字符在不在给定序列中？如果在的话，重复出现了又该如何处理？
备战面试刷题的经验告诉我，这里可用到一个特殊的哈希表来处理上述两个问题。
我们可以定义一个长度为256的int数组来当作我们的哈希表，长度为什么是256？因为ASCII码！我们可以用字符的ASCII码来直接索引定位到该字符。
下面是我个人的解题思路。首先要把哈希表初始化，把序列中存在的字符全部置1，否则置0。然后开始用一个两层嵌套的while循环，第一层循环用来移动下标，第二层则用来标识当前连续的合法字符个数，当个数等于序列长度并且全部合法时即求得解。
还是要唠叨一下哈希表的使用问题，在第二层循环里，我们用到哈希表来判断字符的合法性，当前字符在哈希表中的值为0则说明该字符不合法。若一个合法字符重复出现的话，我们该怎么处理呢？这里，考虑到序列中不重复，每当我们遇到一个合法字符，我们就把该字符在哈希表中的值改为0，也就是后续再重复出现的话，他就成为了不合法字符。（这种做法会产生一个问题，就是我们更改了哈希表，所以我们要在每次进入第二层循环之前，重新初始化哈希表。）
后续：
你以为我应该在这里放代码了？我偏不！与二面一样，面试官又给我加了进阶版的题目。
如果将不重复序列改成可能重复的序列要怎么解决？
例如
可重复序列[a，b，c，d，b]
字符串adcebdbcbadcbd
返回5
这里我就不多说了，经过思考，我发现只要更改掉上面的哈希使用方法即可适配这个进阶版题目。也就是把置0和置1操作变成，在初始化的时候全置0后再加1（不是直接置1），判断合法性的时候是减1（不是直接置0）。你品，你细细的品！
我的做法还有优化的空间，我目前的优化思路是在下标移动上做一些文章，比如，当一个不存在于序列中的字符e出现了，这个时候我们直接把下标移动到e的后面，而不是简单的在a的位置基础上加1。（然而我并没有去实现这个需求）
如果大佬们还有更好的办法，请带带我这个菜鸡！
唠叨太多了，下面放代码吧！
C++代码：
这里放的代码是兼容上面两问的。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
static int hash[256];
inline void CleanHash(vector<char> set){//重置哈希表
for(int i = 0; i < 256; ++i){
hash[i] = 0;
}
for(int i = 0; i < set.size(); ++i){
hash[set[i]]++;
}
}
int Find(vector<char> set, string str){
if(str.length() < set.size()) return -1; //处理特殊情况
int num = 0;//记录当前连续合法字符长度
int index = 0; //记录下标位置
while(index <= (str.length() - set.size())){
//cout << index << endl;
CleanHash(set);
num = 0;
while(num < set.size()){//合法性判断
if(hash[str[index]] != 0){
hash[str[index]]--;
index++;
num++;
}
else{
break;
}
}
if(num == set.size()) return index - num;
index -= num-1;//此处可优化
}
return -1;
}
int main(int argc, char** argv) {
vector<char> set;
set.push_back('a');
set.push_back('d');
set.push_back('c');
set.push_back('b');
set.push_back('b');
string str("adcebdbcbadcbd");
cout << Find(set,str);
return 0;
}
cpp
