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

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

概述

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),不再赘述。

哈希表一次性遍历

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

实现的时候注意三点:

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/