朱晓峰

一只生之无趣死之乏味的丧家之犬

0%

[算法训练]LeetCode 3: 无重复字符的最长子串

Posted on Edited on In

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

无重复字符的最长子串

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

示例 1:

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

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

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

Related Topics: 字符串 滑动窗口

思路

惯例，首先思考一下暴力方法，是会超时还是爆内存，再考虑优化的方法。

暴力方法

遍历每一个字符ai，再往后遍历aj ( j > i )，如果存在aj = ak ( i ≤ k < j )，则比较之前长度的最大值并保存，maxLength = max(maxLength, j - i)

最坏的情况下，时间复杂度为O(n3)

优化

很显然，暴力算法做了很多重复工作，比如

abcabcbb

当找到第二个a的时候，我们已经知道这两个a之间的字符b c是没有重复的，所以不用再反复比较了。

自然而然会想到用滑动窗口的方式来优化。

1
2
3
abcabcbb → abcabcbb → abcabcbb → abcabcbb
↑↑       → ↑ ↑      → ↑  ↑     →  ↑ ↑    
ij       → i j      → i  j     →  i j

用两个指针i和j，让j开始向后滑动，当出现j指向的内容与前面重复（即aj = ak ( i ≤ k < j ) ），则将i往后移动一位，在移动过程中j-i的最大值就是答案。

但是关键是怎么快速判断是否重复，重新审题，字符都是ASCII码，所以可以构造一个长度为256的布尔数组（甚至128就够了），该字符的ASCII码数值则为索引，值用来标记是否已经访问过。

在j往后移动的过程中，将arr[a[j]]设置为true；

在i往后移动的过程中，将前一位arr[a[i-1]]设置为false

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
	def lengthOfLongestSubstring(self, s):
		a = [False] * 256
		length = len(s)
		i, j = 0, 0
		res = 0
		while j < length:
			if i < j and a[ord(s[j])]:
				a[ord(s[i])] = False
				i += 1
			else:
				a[ord(s[j])] = True
				j += 1
			res = max(res, j - i)
		return res

如果大家有更好的解法，恳请不吝赐教，谢谢！