# 题目

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, 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.

# 解题思路

public int lengthOfLongestSubstring(String s) {
//指向正在遍历的字母的指针
int start = 0;
int end = -1;
//指向最长的子串的开头结尾的指针
int resStart = 0;
int resEnd = -1;
//指向上一个子串的指针
int tmpStart = 0;
int tmpEnd = -1;
//用来存储不重复的字符，值表示字符所在位置
HashMap<Character, Integer> set = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
//如果发现字符重复，进行一系列操作
if (set.containsKey(s.charAt(i))) {
//先保留这个子串，方便map删除
tmpStart = start;
tmpEnd = end;
//如果正在遍历的子串长度大于之前的最大值，就替换
if (end - start + 1 >= resEnd - resStart + 1) {
resStart = start;
resEnd = end;
}
//重新设置开始值为重复的字符的下一位
start = set.get(s.charAt(i)) + 1;
end = i;

//如果与前一位相同，直接清空map
if (s.charAt(i) == s.charAt(i - 1))
set.clear();
else {
//否则仅清空相同位之前的字符
int index = set.get(s.charAt(i));
for (int k = tmpStart; k <= index; k++) {
set.remove(s.charAt(k));
}
}
} else {
//不重复，直接向后遍历
end++;
}
//把不重复的字符加入map
set.put(s.charAt(i), i);
}
//因为存在最后一位字符所在的子串刚好是最长的可能，而这时又不会触发上方的语句，所以需要在结尾加个判断
return resEnd - resStart + 1 > end - start + 1 ? resEnd - resStart + 1 : end - start + 1;
}

39 篇文章30 人订阅

0 条评论

## 相关文章

1664

972

1K1

### C++中函数重载、隐藏、覆盖和重写的区别

C++规定在同一作用域中，同名函数的形式参数（指参数的个数、类型或者顺序）不同时，构成函数重载。

982

3568

542

3437

1617

913

### LeetCode <BT> 200. Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands...

430