LeeCode[3] - 无重复字符的最长子串

发表于 | 分类于 |

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例1:

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串

解法(C语言)：

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
int lengthOfLongestSubstring(char * s){
    int length = (int)strlen(s);
    if (length < 2) {
        return length;
    }
    int longest = 1;
    int start = 0;
    int end = 1;
    for (end = 1; end < length; end++) {
        //下一位参与比较的字符
        char end_s = s[end];
        
        //end_s 是否在前面的子串中出现过
        int isExist = 0;
        //将end_s与start到end间的字符进行比较
        for (int j = start; j < end; j++) {
            char start_s = s[j];
            //如果找到相等字符j，将start索引指向j后一位
            if (start_s == end_s) {
                isExist = 1;
                //记录本次字串长度(这里的end已经后移一位了，不需要+1）
                if (end - start > longest) {
                    longest = end - start;
                }
                start = j + 1;
                break;
            }
        }
        if (isExist == 0) {
            if (end - start + 1 > longest) {
                longest = end - start + 1;
            }
        }
        
    }
    return longest;

}