3. 无重复字符的最长子串
2018-09-26 本文已影响0人
莫小鹏
题目描述
给定一个字符串，找出不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc"，其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b"，其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke"，其长度为 3。
请注意，答案必须是一个子串，"pwke" 是一个子序列 而不是子串。
分析
使用hash表记录字符上一次出现的位置
不重复字符的最长子串的长度为i - begin
初始：
begin = 0
max = max(maxLen, i - begin)
str = "abcabcbb"
| i的位置 | 当前字符 | begin | hash | maxLen |
|---|---|---|---|---|
| 0 | a | 0 | {a:0} | 0 |
| 1 | b | 0 | {a:0,b:1} | 0 |
| 2 | c | 0 | {a:0,b:1,c:2} | 0 |
| 3 | a | 1 | {a:1,b:1,c:2} | 3 |
| 4 | b | 2 | {a:1,b:4,c:2} | 3 |
| 5 | c | 3 | {a:1,b:4,c:5} | 3 |
| 6 | b | 3 | {a:1,b:6,c:5} | 3 |
| 7 | b | 3 | {a:1,b:7,c:5} | 3 |
代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length();
vector<int> m(128, -1);
int maxLen = 0;
int begin = 0;
for(int i = 0; i < n; i++) {
char c = s[i];
int pos = m[c];
if(pos >= begin) {
maxLen = max(maxLen, i - begin);
begin = pos + 1;
}
m[c] = i;
}
maxLen = max(maxLen, n - begin); //最后一次
return maxLen;
}
};
题目链接
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/description/
