题目描述

实现代码

// 无重复字符的最长子串
int lengthOfLongestSubstring(string s) {
    int l = 0,r = 0;
    int res = 0;
    unordered_map<char,int> temp;
    while(l < s.size()){
        temp[s.at(l)] = l;
        for (r = l + 1; r < s.size() ; r++) {
            if(temp.count(s.at(r))) break;
            else temp[s.at(r)] = r;
        }
        res = max(res,r - l);
        l ++;
        temp.clear();
    }
    return res;
}

• 这样做不就是暴力搜索吗，复杂度是n平方，有很多优化的地方
  • 不满足条件的时候，并不一定需要重投开始遍历，至少你能确保你将要退出来的是有重复的，将要加进去的是没有重复的，这样就不是平方的运算复杂度，是n的复杂度。

更高效率的实现代码

• 双指针问题，通过单调性来优化，下面的代码写的真好看

int lengthOfLongestSubstring(string s) {
    unordered_map<char,int> heap;
    int res = 0;
    for (int i = 0 ,j = 0; i < s.size(); ++i) {
        heap[s[i]] ++;
        while(heap[s[i]] > 1)
            heap[s[j ++]] --;
        res = max(res,i - j + 1);
    }
    return res;
}

• 这个和我的差不多，都使用了双指针的，按时我没有优化，应该记录一下，他这里写的很简洁，很棒，最后一直将j移动到i重复出现的位置，但是也是一次一次迭代过去的，不够快。

分析总结

• 这次写的还行，但是逻辑没有理清楚，导致出现了很多问题，调整就调了大半天。