1.无重复字符的最长字串
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串 的长度。
示例 1:
1
2
3
| 输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
|
示例 2:
1
2
3
| 输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
|
示例 3:
1
2
3
4
| 输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
|
1
2
3
| int lengthOfLongestSubstring(char* s) {
}
|
2.个人思路
看着不是太难，但是摸索了好久，不断调试。但是还不不完整，这个k值，不应该从0开始，而是从上一次重复的位置开始。从0开始，如果无重复字符在后面，就不行了。前两个可以通过测试，第三个因为两个ww先开始重复了，wke在后面。。。。继续调试。
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
| #include "stdio.h"
#include "string.h"
int demo(char *s)
{
int ret = 0,j=0,max = 0;
int cnt = 1;
char *temp = s;
for (int i = 0; i < strlen(s); ++i) {
for (int k = 0; k < i; ++k) {
if(temp[i] == s[k]) {
cnt = k+1;
break;
}
printf("%c = %c //" ,temp[i],s[k]);
}
if(cnt > max)
max = cnt;
printf("cnt= %d\n",cnt);
}
printf("%d",max);
return ret;
}
int main()
{
char *s1 = "abcabcbb";
char *s2 = "bbbbb";
char *s3 = "pwwkew";
demo(s1);
return 0;
}
|
突然有灵感，加了一个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
| #include "stdio.h"
#include "string.h"
int demo(char *s)
{
int ret = 0,j = 0,max = 0;
int cnt = 1;
char *temp = s;
for (int i = 0; i < strlen(s); ++i) {
for (int k = j+1; k < i; ++k) {
if(temp[i] == s[k]) {
j = k;
cnt = 1;
break;
}
else
{
cnt ++;
}
printf("temp[%d]:%c = s[%d]:%c //" ,i,temp[i],k,s[k]);
}
if(cnt > max)
max = cnt;
printf("cnt= %d\n",cnt);
cnt = 1;
}
printf("%d",max);
return ret;
}
int main()
{
char *s1 = "abcabcbb";
char *s2 = "bbbbb";
char *s3 = "pwwkew";
demo(s2);
return 0;
}
|
但是测试字符串 au 的时候，输出了1。。。。看了一会发现，是k值和j值产生了偏移，字符串太少的话导致第二个for循环不运行了。
修改后的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| int lengthOfLongestSubstring(char* s) {
int ret = 0,j = 0,max = 0;
int cnt = 1;
char *temp = s;
for (int i = 0; i < strlen(s); ++i) {
for (int k = j; k < i; ++k) {
if(temp[i] == s[k]) {
j = k+1;
cnt = 1;
break;
}
else
{
cnt ++;
}
}
if(cnt > max)
max = cnt;
cnt = 1;
}
return max;
}
|
通过！！！！！ 11ms，击败33.03%，8.66MB，击败73.27%，时间复杂度为O(N^2)。
感觉自己写的太lowl了，一道题想了一个小时。。。。
阐述一下个人思路：
一开始想的是while循环，一一比对，但很快发现思路是错的，然后换两个for循环。其中还有些波折，发现sizeof函数不能准确获得长度，然后换用strlen，然后就是后一位字符对比前每一位字符，但是发现如果重复的字符串比较靠后，就不太行，发现要从重现重复的字符位置开始往后比较。题目不难，难在慢慢调试。
3.官方解析
看一下别人的思路吧，我的也是正确的。
滑动窗口:
我们不妨以示例一中的字符串 abcabcbb 为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：
1
2
3
4
5
6
7
8
| 以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb
以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb
以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb
以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb
以 abca(b)cbb 开始的最长字符串为 abca(bc)bb
以 abcab(c)bb 开始的最长字符串为 abcab(cb)b
以 abcabc(b)b 开始的最长字符串为 abcabc(b)b
以 abcabcb(b) 开始的最长字符串为 abcabcb(b)
|
太妙了，一个for循环就能完成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #define MAX(a, b) ((b) > (a) ? (b) : (a))
int lengthOfLongestSubstring(char* s) {
int ans = 0, left = 0;
bool has[128] = {};
for (int right = 0; s[right]; right++) {
char c = s[right];
while (has[c]) {
has[s[left]] = false;
left++;
}
has[c] = true;
ans = MAX(ans, right - left + 1);
}
printf("%d",ans);
return ans;
}
|
时间复杂度为O(N)。
