无重复字符的最长子串

最近更新于 2023-04-01 09:14

题目

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

示例 1:

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

示例 2:

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

示例 3:

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题

滑动窗口

定义两个指针 left 和 right，分别指向查找中的无重复子串的左右边界，初始 left 指向第一个字符，right 指向第二个字符。
外层循环每次将右指针向后移动一次，内层循环负责遍历从 left 到 right 的前一个字符，将它们挨个和 right 位置的值比较，如果 left 到 right 前一个字符之间存在和 right 位置相同的字符，则将 left 移动到出现重复字符的位置的下一个字符的位置，并退出内层循环，外循环也会向后移动一位；如果遍历完都没找到和 right 位置相同的，则此轮内层循环完成遍历后，计算 left~right 之间有多少个字符，并和已经记录的最大值比较，最终记录最大的值。
时间复杂度为 O(n^2)

int lengthOfLongestSubstring(char * s)
{
    int len = strlen(s);
    if (len == 0)
    {
        return 0;
    }

    int max = 1;

    for(int i, left = 0, right = 1; right < len; ++right)
    {
        for(i = left; i < right; ++i)
        {
            if(s[i] == s[right])
            {
                left = i + 1;
                break;
            }
        }
        if(i == right && right - left + 1 > max)
        {
            max =  right - left + 1;
        }
    }
    return max;
}

滑动窗口 + 哈希表

算是上一种方法的改进，主要变化就是在查找方法上，上一个是线性查找，要挨个遍历元素，这里换成了哈希表，在查找算法上的时间复杂度从O(n)降为了O(1),总体时间复杂度则变成了O(n)。这里力扣显示的执行时间差不多，应该是数据量小的原因，体现不出差距，如果数据量非常大就会很明显了。
这里的字符串组成都是ASCII码，所以就定义了一个128大小的数组（哈希表），用于保存最近出现某个字符的位置（的下一个位置下标）。循环每次将右指针向后移动一位，然后比较 left 和最近一次重复某个字符的位置的（下一位的）下标，有重复就将左指针移动到重复位置的下一位，然后计算左右指针之间的字符数和之前记录的最大值比较，记录最终的最大值，然后又记录当前right位置的字符的下标的下一位。

注：fmax 是数学库中的函数，用于找出两个数中的最大值

int lengthOfLongestSubstring(char *s)
{
    int len = strlen(s);
    int max = 0;
    int index[128] = {0};

    for (int left = 0, right = 0; right < len; ++right)
    {
        left = fmax(left, index[s[right]]);
        max = fmax(max, right - left + 1);
        index[s[right]] = right + 1;
    }
    return max;
}