longest-substring-without-repeating-characters
题目描述
Given a string, find the length of the longest substring without repeating characters.
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
1
2
3
| 输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
示例 2:
1
2
3
| 输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
|
示例 3:
1
2
3
4
5
| 输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 **子串** 的长度，"pwke" 是一个子序列，不是子串。
|
我的思路
One
- 刚开始想耍一些”小聪明”，看有没有巧妙的方法解决，当时用了类似于Node的前后’指针’的方式发现有些用例是过不了的
- 后面用到了类似”滑窗”的方法，碰到重复字符则将滑窗宽度归零，且位置回到被重复字符的下一位置。
- 但会出现死循环，因为没把之前被重复的字符
remove掉 – 后面发现只remove掉那个重复的字符的话，有些没有重复的字符在回退之后再次计算的时候，会发生混乱(回退后再次走到之前不重复的字符时候，因为hash表中已经在第一次put过了，所以这次一定会发生重复情况) - 所以上面把滑窗归零的时候是真正的归零，包括存数据的hash表
上面方法应该是 $ O(n^2) $ ,因为会发生例如abcdea在最后a发生重复，就会完全回退到b位置—so low ；提交记录耗时大概80+ms
Two
- 第二个方法是也两个指针类似滑窗， k指针一直前进，发生重复时j指针移动到被重复字符的下一位置，但是只能往右移动，不能回退
- 将
map<Character,Integer>中存放的之前被重复字符的value(即字符所在的索引)换为当前发生重复的字符位置 – 不是被重复字符 - 循环中一直保持
max最大 - 当有其中一个指针到达终点时，就可以退出了 ；由于
j,k代表的都是索引，所以最后结果 为max+1
Three
- 第二种方法发现 k一直在++，其实就相当于for循环的 i++，所以就换成for循环了 – 复杂度应该是 $ O(n) $
Two和Three 提交的耗时6ms,占用内存35M–占用内存竟然超过了 100%的java用户ヽ(°◇° )ノ
我的代码
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| package com.dasnnj.practice.medium;
import java.util.HashMap;
import java.util.Map;
public class LongestSubstringWithoutRepeatingCharacters {
public static void main(String[] args) {
LongestSubstringWithoutRepeatingCharacters l = new LongestSubstringWithoutRepeatingCharacters();
System.out.println(l.lengthOfLongestSubstring(""));
}
public int lengthOfLongestSubstring(String s) {
if ("".equals(s)) {
return 0;
}
char[] chars = s.toCharArray();
int j = 0, k = 0, max = 0;
Integer ele;
Map<Character, Integer> sets = new HashMap<>(16);
for (int m = 0; m < chars.length; m++) {
if ((ele = sets.get(chars[m])) != null) {
if (j < ele + 1) {
j = ele + 1;
}
}
sets.put(chars[m], m);
if (max < m - j) {
max = m - j;
}
}
return max + 1;
}
}
|