LeetCode刷题之旅(3)--无重复字符的最长子串(中等题)

没有简单的题目,或者说,再简单的题目,只要追求极致,都会要花心思。好好加油吧<->

题目:无重复字符的最长子串

1
给定一个字符串,找出不含有重复字符的最长子串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例1:
输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc",其长度为 3。

示例2:
输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b",其长度为 1。

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

解题思路:

方法1:

首先,因为键盘可输入字符为128个,所以先int一个128的数组并且初始化为0,用此数组来记录是否重复,然后在循环中判断,如果为0,那么就累加长度,并且记录最大长度。然后在不为0的时候,再初始化数组为0。很明显,这个初始化很耗时,所以又想了下面的方法。

方法2:

双游标,i,j两者之差j-i+1就是子串的长度,然后数组记录的不再是字符是否重复了,而是记录最后一个字母在s串中的位置。细节在于,i在字母重复的时候,会变成字母所在的位置,判断的时候的细节在于,重复的字母的位置如果在i的左边,则表示不会在i到j的子串中重复。

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
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int arr[128]={0};
int max_length=0,i,j;
for(i=0,j=0;j<s.size();++j)
{
if(arr[(int)s[j]]==0||arr[(int)s[j]]-1<i)
{
arr[(int)s[j]]=j+1;//保持字符 s[j] 在s中的位置+1 比如0位 ,最后保存的是1
//length++;
if(j-i+1>max_length)
{
max_length=j-i+1;
}

}
else
{
if(arr[(int)s[j]]-1<i)
{

}
else
{
i=arr[(int)s[j]];
arr[(int)s[j]]=j+1;
/*if(j-i>max_length)
{
max_length=j-i+1;
}*/
}


}
}

return max_length;


}
};
static const auto _____ = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return nullptr;
}();
执行用时:12 ms
您的支持将鼓励我继续创作!