# 引言
题目链接：https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
# 题目大意
输入一个字符串, 输出没有重复字符的最长子串的长度。
例：
- 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.
# 题解
# 一句话题解
利用map或者hash表映射字符和字符上一次出现的位置, 当遇到重复字符时(当前符合条件子串结束), 查找下一个不包含重复字符的子串起点, 同时把当前子串的长度和已有最大值比对记录
- 详解
映射关系中, 保存当前字符在字符串已查询部分中最后出现的下标位置(默认-1,没有出现过)
- 默认第一个子串起点下标为0
- 最大值为当前下标和起点下标的差值与存储的最大值的较大者
- 当查询到当前字符已经出现过, 分两种情况讨论
- 当前子串的起点下标
>当前查询字符上一次出现下标位置(证明当前查询字符在当前子串未出现过, 如tmmzuxt,查询最后一个t当前子串起点为第二个m) - 当前子串的起点下标
<=当前查询字符上一次出现下标位置(证明当前查询字符在当前子串已经出现过一次, 当前字符串终结, 如wkew, 查询最后一个w当前子串起点为第一个w)
- 当前子串的起点下标
综上所述, 情况一当前子串起点位置大于查询字符上一次出现位置, 字符在子串第一次出现, 保持起点不变即可, 情况二当前子串起点位置小于查询字符第一次出现位置, 字符在子串第二次出现, 当前子串终结, 下一个子串起点重置为当前查询字符出现的下一个下标
即 lastDiffIndex = lastDiffIndex > index + 1 ? lastDiffIndex : index + 1;
复杂度O(n)
# AC代码
c++版本
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
int maxn = 0;
int lastDiffIndex = 0;
int indexHash[256];
memset(indexHash, -1, sizeof(indexHash));
for (int i = 0; i < s.length(); ++i)
{
int index = indexHash[s[i] - '\0'];
if (-1 != index)
{
lastDiffIndex = lastDiffIndex > index + 1 ? lastDiffIndex : index + 1;
}
indexHash[s[i] - '\0'] = i;
maxn = maxn > i - lastDiffIndex + 1 ? maxn : i - lastDiffIndex + 1;
}
return maxn;
}
};go版本
func lengthOfLongestSubstring(s string) int {
var maxn, lastDiffIndex int
indexMap := make(map[int32]int)
for i, ch := range s {
index, ok := indexMap[ch]
if ok {
if index+1 > lastDiffIndex {
lastDiffIndex = index + 1
}
}
indexMap[ch] = i
if i-lastDiffIndex+1 > maxn {
maxn = i - lastDiffIndex + 1
}
}
return maxn
}
有什么想法，欢迎留下评论。