题目描述
Given a string, find the length of the longest substring without repeating characters.
Note:
The input string length won’t exceed 1000.
Example1:
Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example2:
Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example3:
Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
解题思路
- 这里可以建立一个 HashMap，建立每个字符和其最后出现位置之间的映射
- 然后需要定义两个变量 res 和 left，其中 res 用来记录最长无重复子串的长度，left 指向该无重复子串左边的起始位置的前一个，由于是前一个，所以初始化就是 -1
- 然后遍历整个字符串，对于每一个遍历到的字符，如果该字符已经在 HashMap 中存在了，并且如果其映射值大于 left 的话，那么更新 left 为当前映射值。
-
然后映射值更新为当前坐标i，这样保证了 left 始终为当前边界的前一个位置，然后计算窗口长度的时候，直接用 i-left 即可，用来更新结果 res。
- 这里解释下程序中那个 if 条件语句中的两个条件 m.count(s[i]) && m[s[i]] > left，因为一旦当前字符 s[i] 在 HashMap 已经存在映射，说明当前的字符已经出现过了，而若 m[s[i]] > left 成立，说明之前出现过的字符在窗口内，那么如果要加上当前这个重复的字符，就要移除之前的那个，所以让 left 赋值为 m[s[i]]，由于 left 是窗口左边界的前一个位置（这也是 left 初始化为 -1 的原因，因为窗口左边界是从0开始遍历的），所以相当于已经移除出滑动窗口了.
- 举一个最简单的例子 “aa”，当 i=0 时，建立了 a->0 的映射，并且此时结果 res 更新为1，那么当 i=1 的时候，发现a在 HashMap 中，并且映射值0大于 left 的 -1，所以此时 left 更新为0，映射对更新为 a->1，那么此时 i-left 还为1，不用更新结果 res，那么最终结果 res 还为1，正确，
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0, left = -1, n = s.size();
unordered_map<int, int> m;
for (int i = 0; i < n; ++i) {
if (m.count(s[i]) && m[s[i]] > left) {
left = m[s[i]];
}
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};
解题思路
- 使用了 HashSet，把出现过的字符都放入 HashSet 中
- 遇到 HashSet 中没有的字符就加入 HashSet 中并更新结果 res
- 如果遇到重复的，则从左边开始删字符，直到删到重复的字符停止
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> t;
int res = 0, left = 0, i = 0, n = s.size();
while(i < n){
if(!t.count(s[i])){
t.insert(s[i]);
i++;
res = max(res, (int)t.size());
}else{
t.erase(s[left]);
left++;
}
}
return res;
}
};
class Solution {
public:
int lengthOfLongestSubstring(string s) {
char windows_set[128] = {0};
int windows_start = 0, windows_end = 0;
int windows_size = 0;
while(windows_end < s.size()){
if(windows_set[s[windows_end]] == 0){
windows_set[s[windows_end]]++;
windows_end++;
windows_size = max(windows_size, windows_end - windows_start);
}else{
windows_set[s[windows_start]]--;
windows_start++;
}
}
return windows_size;
}
};
