Leetcode题解剑指 Offer 48. 最长不含重复字符的子字符串

PROBLEM

难度中等

MY ANSWER

基本滑动窗口，维护窗口内不能有重复字符，记录窗口最大值返回。遍历字符串，若新字符不重复，则窗口右边缘向右扩展一位；若重复，则左边缘向右收缩直到窗口左边第一个是之前窗口的重复字符。因调用字符串的find函数，时间复杂度O(n^2)，空间复杂度O(1)。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty()) {
            return 0;
        }
        int max = 1;
        int end = 1;
        int start = 0;
        for(int i = 1; i < s.size(); i++) {
            size_t fpos = s.substr(start, end).find(s[i]);
            if(fpos == string::npos) {
                end++;
                if(end > max) {
                    max = end;
                }
            }
            else {
                start += fpos + 1;
                end = end - fpos;
            }
            // cout<<"start"<<start<<endl;
            // cout<<"end"<<end<<endl;
        }
        return max;
    }
};

BETTER SOLUTIONS

查找窗口中是否有重复字符时，可以使用哈希表让时间复杂度下降到O(n)。遍历时将字符加入哈希表中，值为当前字符的位置。因为ascii字符只有128个，所以空间复杂度O(1)。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> m;
        int ret = 0, l = 0, r = 0;
        while (r < s.size()) {
            if (m.find(s[r]) != m.end()) {
                l = max(l, m[s[r]] + 1);
            }
            m[s[r++]] = r;
            ret = max(r - l, ret);
        }
        return ret;
    }
};

SUMMARY

哈希表降低查找复杂度；
理解滑动窗口思想。