剑指 Offer 48 最长不含重复字符的子字符串
概述
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