剑指 Offer 48 最长不含重复字符的子字符串

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-26 23:32:47
    编辑于：2022-02-27 09:38:52
    浏览量：784

概述

https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/

https://leetcode.com/problems/longest-substring-without-repeating-characters/

暴力遍历

O(n^2) 时间复杂度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, bool> visited;
        int ans = 0;
        for (int i = 0; i < s.size(); i ++) {
            visited.clear();
            int count = 0;
            for (int j = i; j < s.size(); j ++) {
                if (visited[s[j]]) break;
                visited[s[j]] = true;
                count ++;
            }
            ans = max(ans, count);
        }
        return ans;
    }
};

动态规划

动态规划也是 O(n^2)，不再赘述。

哈希表一次性遍历

哈希表记录字符是否出现以及上次的出现次数，遍历的同时维护当前字符串的起始位置。

实现的时候注意三点：

即使哈希表中存在该字符，我们还需要检查该字符是否过时：if (m[s[i]].first && m[s[i]].second >= start)
注意这里的类型转换：int(s.size()) - start
注意要在循环结束后更新一次 ans：ans = max(ans, int(s.size()) - start);

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, pair<bool, int>> m;  // default value <false, 0>
        int ans = 0;
        int start = 0;
        for (int i = 0; i < s.size(); i ++) {
            if (m[s[i]].first && m[s[i]].second >= start) {
                ans = max(ans, i - start);
                start = m[s[i]].second + 1;
                m[s[i]].second = i;
            } else {
                m[s[i]] = {true, i};
            }
        }
        ans = max(ans, int(s.size()) - start);
        return ans;
    }
};

Links: sword-offer-48