导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一
    2. 方法二
    3. 方法三

LeetCode-3.Longest Substring Without Repeating Charaters

题目

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb” , the answer is “abc” , which the length is 3.

Given “bbbbb” , the answer is “b” , with the length of 1.

Given “pwwkew” , the answer is “wke” , with the length of 3. Note that the answer must be a substring , “pwke” is a subsequence and not a substring.

翻译

给出一个字符串,找到其没有重复字符的 最长子串 的长度。
例如:
给出 “abcabcbb” ,答案是 “abc” ,其长度为3。
给出 “bbbbb” ,答案是 “b” ,其长度为1。
给出 “pwwkew” ,答案是 “wke” ,其长度为3。
注意答案必须是一个 子字符串 “pwke” 是一个序列而不是子串。

方法一

看到题目第一反应就是滑动窗口法,设定左和右两个指针left和right,作为窗口的起止。
right不断步进,每次判断新字符是否已经出现过,如果有重复,则循环步进left,直至找到重复字符所在位置停止。
利用一个set记录已经出现过的字符,当left和right步进时更新:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0, right = 0, res = 0;
Set<Character> chars = new HashSet<Character>();

while (right < s.length()) {
if (chars.contains(s.charAt(right))) {
res = Math.max(res, right - left);
while (s.charAt(left) != s.charAt(right)) {
chars.remove(s.charAt(left));
left++;
}
left++;
right++;
} else {
chars.add(s.charAt(right));
right++;
}
}
res = Math.max(res, right - left);

return res;
}
}

时间复杂度为2n,即O(n)

方法二

将方法一种的set,替换为一个boolean数组,记录每个字符是否出现过。
在Java中,char类型代表一个unicode字符,占两字节,16位,共65536个字符。
转换为int后输出可见:
Character.MIN_VALUE = 0
Character.MAX_VALUE = 65535
将所有字符写入文件可知,A-Z为68-93,a-z为100-125。
而题中未指定字符范围,因此,设定范围从空格符(32)开始,到“~”符(126)结束,共95个字符,概括了常见字符,也是键盘上可以打出的所有半角字符:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0, right = 0, res = 0;
boolean[] chars = new boolean[95];

while (right < s.length()) {
if (chars[s.charAt(right) - ' '] == true) {
res = Math.max(res, right - left);
while(s.charAt(left) != s.charAt(right)) {
chars[s.charAt(left) - ' '] = false;
left++;
}
left++;
right++;
} else {
chars[s.charAt(right) - ' '] = true;
right++;
}
}
res = Math.max(res, right - left);

return res;
}
}

时间复杂度为2n,即O(n)

方法三

将方法二中的boolean数组,替换为一个int数组,记录遇到的每个字符,最近一次出现的index。
当right遇到重复字符时,直接将left设定为index+1,省略循环操作,提高效率:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0, right = 0, res = 0;
int[] locs = new int[95];
for (int i = 0; i < 95; i++) locs[i] = -1;

while (right < s.length()) {
if (locs[s.charAt(right) - ' '] >= left && left != right) { // 新字符在当前子串中;当字串长度为1时不更新left
res = Math.max(res, right - left);
left = locs[s.charAt(right) - ' '] + 1;
}

locs[s.charAt(right) - ' '] = right;
right++;
}
res = Math.max(res, right - left);

return res;
}
}

时间复杂度为n+C,即O(n)

参考:
http://www.cnblogs.com/dollarzhaole/p/3155712.html
http://articles.leetcode.com/longest-substring-without-repeating-characters