一周一个ARTS计划
- Algorithm: 一个leetcode算法题
- Review: 点评（或翻译学习）一篇英文技术文章
- Tip: 学习一个技术技巧
- Share: 分享一个技术观点和思考
A
无重复字符的最长子串1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69// 自己的版本，最开始用的List时间太慢，后来改用数组，同时出现了两个地方的问题
// 该版本的运行时间在整体提交中处于48%的位置，达不到合格
public class Solution {
public int lengthOfLongestSubstring(String s) {
char[] array = s.toCharArray();
int max = 1;
if ("".equals(s)) { // 1、注意空字符串判断
return 0;
}
for (int i = 0; i < array.length - max; i++) {
char aa = array[i];
int fromIdx = i + 1;
int[] test = new int[255];
test[aa] = 1;
for (int i1 = fromIdx; i1 < array.length; i1++) {
char b = array[i1];
if (test[b] != 1) {
test[b] = 1;
if ((i1 + 1) == array.length) {// 2、整个字符串没有重复的场景
max = array.length - i;
}
} else {
if ((i1 - i) > max) {
max = i1 - i;
}
break;
}
}
}
return max;
}
}
// 版本2 对第一个版本做了变种，从两个for变成一个for循环，但因为重置了，最后发现本质上没区别
// 运行结果提升到了60%, 看上去有小提升，但复杂度更高
public class Solution {
public int lengthOfLongestSubstring(String s) {
char[] array = s.toCharArray();
int max = 0;
if (!"".equals(s)) {
int[] test = new int[255];
int move = 0;
int temp = 0;
for (int i = 0; i < array.length; i++) {
char aa = array[i];
if (test[aa] != 1) {
test[aa] = 1;
if ((i + 1) == array.length) {
temp = array.length - move;
if (temp > max) {
max = temp;
}
}
} else {
temp = i - move;
if (temp > max) {
max = temp;
}
i = move; // 关键部分 重置循环下标
move++; // 关键部分 移动偏移下标
test = new int[255]; // 关键部分 重置为0状态
}
}
}
return max;
}
}
// 标准答案版本 fixme