Leetcode之3-无重复字符的最长子串(Longest Substring Without Repeating Characters)

算法题

题干

给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

思路

字符串s的无重复字符的最长子串有可能存在多个, 而且是以字符串s中某(几)个字符开头的字符串(貌似是废话)。题干中明确表明无重复字符, 那么我们如何确保字符已经被访问过? 很简单, 将字符访问状态存储下来就好。解题思路与乘积小于k的子数组类似, 通过滑动窗口来解答。

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() <= 0) {
return 0;
}
final int LEN = s.length();
int result = 0, start = 0, end = 0;
boolean[] appeared = new boolean[256];
while (start < LEN && end < LEN) {
while (end < LEN && !appeared[s.charAt(end)]) {
appeared[s.charAt(end)] = true;
end++;
}
result = Math.max(result, end - start);
appeared[s.charAt(start)] = false;
start++;
}
return result;
}

代码解析

  1. 第6行代码result代表最长无重复字符子串长度, start表示循环遍历字符串s的游标, end表示以start处字符开头的最长无重复字符子串的最后一个字符的索引值加1(不知道大家是否清楚)。
  2. 第7行代码appeared数组用来表示字符是否在字符串s中出现过。
  3. 第9-12行代码表示找无重复字符子串的最后一个字符位置。
  4. 第13行代码用于计算最长无重复字符子串的长度。
  5. 第14行代码用于将start处的字符标志位设置为false, 因为start游标往后移动的话, 之前start位置字符与后面的无重复字符子串中已经无关。
如果有任何错误或疑问, 欢迎小伙伴们评论区留言^-^
( 完 )

欢迎各位看官关注

麻辣烫,走起
0%