LeetCode 003 Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

本文主要讲解LeetCode 3 Longest Substring Without Repeating Characters算法的理解,网上的Solution有好几种,但是一头扎进去看,还有点云里雾里的(主要是我太菜),所以搞个图来加深下理解,并记录下

图片理解

如下图
map:来存储字符的最新游标
index:遍历游标
start:最新子串的起始位置,计算方式就是取出index处字符上次记录的位置和start之间的最大值
max:最大子串长度,计算方式就是取max和(index - start + 1)之间的最大值

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
int start = 0;
int index = 0;
int max = 0;

for (int len = s.length(); index < len; index ++) {
char c = s.charAt(index);
Integer pIndex = map.get(c);
if (pIndex != null) {
start = Math.max(start, pIndex + 1); //合理的start
}
max = Math.max(max, index - start + 1); //合理
map.put(c, index);
}
return max;
}
}

小结

算法已经分析完了,通过绘图,一步一步的分析,找到解决问题的关键元素start,以及start的计算和max计算方式,那么问题就迎刃而解了。