LeetCode 3. Longest Substring Without Repeating Characters

题目描述

题目链接

思路

  1. 假设必须以i位置字符结尾的字符串最大不重复字串的长度是x,那么所有位置x值中最大的值就是答案。

  2. i位置的x的值取决于两个因素。

    • 第一个因素是i-1向左边能扩到最左位置(即:i-1位置上的x值)。
    • 第二个因素是i位置的值上一次出现的位置。

这两个因素取最大值即可算出i位置的x的值。

比如

1
[b,c,1,a,a,x,3,4,b,4]

这个字符串,我们要求第4个位置a这个字符的x值是多少?

此时:i=4

先看上面说的第一个因素:i-1位置(即3号位置上的a)能向左边扩到的最左位置是0位置(赋给变量mostLeft),

第二个因素:i位置的a字符上一次出现的位置是3位置(赋给变量prePos),

所以i位置的x值就是:

1
i - max(mostLeft, prePos) = 4 - max(0, 3) = 4 - 3 = 1
  1. 如何记录i位置上一次出现的位置呢?

可以用一个整型数组arr来表示

比如:

a 的 ascii码是97, arr[97] = 3,表示a上次出现的位置是3。

  1. 如何记录i向左扩能扩到最左的位置是哪里? 可以用一个pre变量来记录,pre初始是-1。

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int max = 1;
int pre = -1;
char[] str = s.toCharArray();
int[] arr = new int[256];
for (char c : str) {
arr[c] = -1;
}
for (int i = 0; i < str.length; i++) {
// 上一次出现的位置
pre = Math.max(arr[str[i]], pre);
max = Math.max(i - pre, max);
arr[str[i]] = i;
}
return max;
}

更多

算法和数据结构笔记

参考资料