[LeetCode] Longest Substring Without Repeating Characters(最长无重复子串问题)

发布于 2018-06-01  4,303 次阅读


(不暴力搜索这方面,不暴搜是不可能不暴搜的,这辈子都不可能不暴搜的,聪明的方法又想不到,哈希表又用不来,就只有用用naive的方法,才维持的了生活这样子)

这个问题真的是折腾死我了,开始根本没想到需要用hash来让搜索变快,直到林和看到最后一个instance的长度。。。(粘贴进VS都会报错的好吗!!)然鹅hash又不太会用,重复的情况怎么排又搞了好久(流下了不学无术的泪水)写完之后发现吧。。。其实真的挺简单的。

关键在于

  1. 使用hash加速搜索过程
  2. 在遇到重复字母的时候一定要注意判断(重复字母与当前子串的)先后顺序和考虑(左指标)需要向右多移动一位的问题
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;
    }
};

终有一日, 仰望星空