无重复字符的最长子串

最近更新于 2024-05-06 07:58

题目

给定一个字符串 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;
}

file

滑动窗口 + 哈希表

算是上一种方法的改进,主要变化就是在查找方法上,上一个是线性查找,要挨个遍历元素,这里换成了哈希表,在查找算法上的时间复杂度从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;
}

file

无重复字符的最长子串
Scroll to top