一道面试题,当时想到有一种最优的解法,可怎么也想不出来了,现在回顾了一下:
函数原型如下:
int getLongestSubString(string s){
}
就是求出一个给定字符串的最长不重复子串的最大长度值是多少。
例如:给定的字符串为"abcdafg",其最长的不重复子串的长度为:6,即":bcdafg"。
最优解法代码如下:
#include<iostream>#include<string>#include<cstdlib>#include<algorithm>using namespace std;int getLongestSubString(const string s){int hash[256]; //hash表中存放的是每一个字符的下标位置;memset(hash, -1, sizeof(hash)); //int prev = 0, max_len = 0; //prev用来存放出现不重复子串的首地址int n = s.length();for (int i = 0; i < n; i++){if (hash[s[i]] != -1){if (hash[s[i]] >= prev){prev = hash[s[i]] + 1;}hash[s[i]] = i;}else{hash[s[i]] = i;}max_len = max(max_len, i - prev + 1);}return max_len;}int main(){string s = "abcdabefgh";cout << getLongestSubString(s)<<endl;}
对上面的代码进行优化:
int lengthOfLongestSubstring(string s) {unordered_map<char, int> hashTable;size_t prev = 0;size_t maxLength = 0;for (int i = 0; i < s.length(); i++) {char c = s[i];if (hashTable.count(c) && hashTable[c] >= prev) {prev = hashTable[c]+1;}hashTable[c] = i;maxLength = max(maxLength, i-prev+1);}return (int)maxLength;}