题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
解题思路
先尝试暴力的解法，从第一字符开始放入set,遇到重复的就停止，记录当前不重复的最大字符个数，最后输出一个最大的。
暴力方法使用了两重循环，其中有大量的无用查找。仔细考虑，如果扫描到一样的，可以从左侧删除一样的，继续向下扫描，这样就可以不用回溯，提高效率。
题解
C++
暴力解决：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.size();
set<char> unique;
int ans = 0;
for (int i = 0; i < len; i ++)
{
int length;
for (int j = i; j < len; j ++)
{
if (unique.find(s[j]) == unique.end())
{
unique.insert(s[j]);
}
else
{
break;
}
}
length = unique.size();
ans = ans > length ? ans : length;
unique.clear();
}
return ans;
}
};
使用哈希表记录元素位置，避免重复扫描。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> m;
int ans = 0;
int left = 0; // 指示左侧开始的位置
for (int i = 0; i < s.size(); i++)
{
left = max(left, m[ s[i] ]); //更新左侧
m[ s[i] ] = i + 1; // 位置从1开始
ans = max(ans, i - left + 1);
}
return ans;
}
};
python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
j = 0
end = len(s)
ans = 0
unique = set()
while(j < end):
i = j
while(i < end):
if s[i] not in unique:
unique.add(s[i])
i = i + 1
continue
else:
break
length = len(unique)
ans = max(ans, length)
unique = set()
j = j + 1
return ans
使用dict存储映射关系，实现一遍扫描出结果。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = 0
m = {}
left = 0
for i, v in enumerate(s):
if v not in m:
m[v] = i + 1
else:
left = max(left, m[v])
m[v] = i + 1
ans = max(ans, i - left + 1)
return ans
