0003 无重复字符的最长子串

中等 滑动窗口

算法思路

本题的思路是滑动窗口。我们可以遍历字符串的每一个字符，并找到以其为开头的一个最长的不重复子串。 不难想象，当我们找到这些子串时，子串的结尾字符索引一定是递增的。

因此，我们通过两个指针 left right 标记找到的子串的收尾索引，每当 right 遇到一个已出现在子串的字符时，就右移 left 直至跳过重复字符。

此算法时间复杂度为 \(O(n)\)，空间复杂度为 \(O(\varepsilon)\)，其中 \(\varepsilon\) 为字符集的大小。

代码实现

longest-substring-without-repeating-characters.c

int lengthOfLongestSubstring(char* s) {
    int letter[128];
    int max = 0, left = 0, right = -1;
    memset(letter, 0, 128 * sizeof(int));
    while (1) {
        while (!letter[s[++right]] && s[right]) {
            letter[s[right]] = 1;
        }
        max = (max > right - left) ? max : right - left;
        if (!s[right]) {
            break;
        }
        while (s[left++] != s[right]) {
            letter[s[left - 1]] = 0;
        }
    }
    return max;
}