(不暴力搜索这方面,不暴搜是不可能不暴搜的,这辈子都不可能不暴搜的,聪明的方法又想不到,哈希表又用不来,就只有用用naive的方法,才维持的了生活这样子)
这个问题真的是折腾死我了,开始根本没想到需要用hash来让搜索变快,直到林和看到最后一个instance的长度。。。(粘贴进VS都会报错的好吗!!)然鹅hash又不太会用,重复的情况怎么排又搞了好久(流下了不学无术的泪水)写完之后发现吧。。。其实真的挺简单的。
关键在于
- 使用hash加速搜索过程
- 在遇到重复字母的时候一定要注意判断(重复字母与当前子串的)先后顺序和考虑(左指标)需要向右多移动一位的问题
class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map<char, int> smap; unordered_map<char, int>::iterator it; int size = s.size(); int i = 0; int len = 1; for (int j = 0; j < size; ++j) { it = smap.find(s[j]); if (it != smap.end()) { //the most important part in my opinion i = max(it->second + 1, i); len = max(len, j - i); } smap[s[j]] = j; len = max(len, j - i + 1); } if (!s.size())return 0; return len; } };
Comments | NOTHING