例子

"abmadsefadd"  最长长度为5

"avoaid"           最长长度为3

 

思路

空间换时间hashTable，起始位置设为beg。初始化全局最大值0。开辟字符数组，起初标为0。

访问数组时

• 如果该字符在hashTable对应的哈希值为1，则计算当前位置到beg的距离，并且把beg赋值为beg+1。如果大于全局最大值，则替换全局最大值
• 如果该字符在hashTable对应的哈希值为0，则置1

参考代码

 

#include 
     
      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;}
     

 

结果

73