例子
"abmadsefadd" 最长长度为5
"avoaid" 最长长度为3
思路
空间换时间hashTable，起始位置设为beg。初始化全局最大值0。开辟字符数组，起初标为0。
访问数组时
- 如果该字符在hashTable对应的哈希值为1，则计算当前位置到beg的距离，并且把beg赋值为beg+1。如果大于全局最大值，则替换全局最大值
- 如果该字符在hashTable对应的哈希值为0，则置1
参考代码
#include <iostream> using namespace std; int getMaxLen(const string &s) { int beg = 0; int span = 0; int maxspan = 0; int hashTable[128]; for (int i = 0; i < 128; ++i) hashTable[i] = 0; int lens = s.size(); for(int i = 0; i < lens; ++i) { int index = s[i]; if (hashTable[index] == 1) { span = i - beg; if (span > maxspan) maxspan = span; beg++; } else { hashTable[s[i]] = 1; } } return maxspan; } int main() { const string a = "abmadsefadd"; const string a1 = "avoaid"; cout << getMaxLen(a) << endl; cout << getMaxLen(a1) << endl; }
结果
|
1
2
|
7
3
|
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3822923.html，如需转载请自行联系原作者
