給定一個字串，請你找出其中不含有重復字符的 最長子串 的長度，
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3，
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1，
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3，
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串，
起初我在進行編程的時候忽視了一點，當字串長度為0的時候應該回傳的是0而不是1，之后我還掌握了map和hash_map的區別，hash_map的底層實作方法為哈希表（時間復雜度為O（1）），而map的底層實作方式是紅黑樹（時間復雜度為O（log（n））），因此我起初使用map的時候會發生超時，最后本題最優的寫法應該是，使用長度為256的桶進行計算，感興趣的同學可以嘗試一下，
#include <cstdio> #include <iostream> #include <cstring> #include <unordered_map> using namespace std; using namespace stdext; int lengthOfLongestSubstring(string s); int main() { string input; cin >> input; cout << lengthOfLongestSubstring(input); return 0; } int lengthOfLongestSubstring(string s) { int len = s.length(); if (len == 0) { return 0; } unordered_map<char, int> stringmap; int maxlen = 1; int begin = 0; int end = 1; while (end <= len) { if (stringmap.find(s.at(end - 1)) == stringmap.end()) { stringmap.insert(pair<char, int>(s[end - 1], end - 1)); if (stringmap.size() > maxlen) { maxlen = stringmap.size(); } end++; } else { begin = stringmap.find(s.at(end - 1))->second + 1; end = begin + 1; stringmap.clear(); } } return maxlen; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40780.html
標籤：C++
上一篇：運營商大資料在不同行業的獲客應用
下一篇：圓桌均分硬幣 ——（推導式子）