3.无重复字符的最长子串

LeetCode LeetCode 哈希表 热题100 字符串 滑动窗口
发布时间 :
字数:3.1k 阅读 : 评论:
  1. 3.无重复字符的最长子串
    1. 3.1 题目
    2. 3.2 题解
      1. 方法一：双循环法
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：滑动窗口单循环缓存字典法
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 3.3 代码
    4. 3.4 运行结果

3.无重复字符的最长子串

3.1 题目

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

示例：

  • 示例 1：

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

  • 示例 2：

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

  • 示例 3：

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

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

3.2 题解

方法一：双循环法

思路

用两层循环枚举所有可能的子串。外层循环确定子串起点，内层循环从起点向后扩展，遇到重复字符就停止。使用 Contains 判断当前字符是否已在子串中出现。

核心思想：暴力枚举所有子串，找到最长的无重复字符子串。

具体步骤：

  1. 外层循环遍历每个可能的起始位置 startIndex。
  2. 内层循环从 startIndex + 1 开始向后扩展：
    • 如果当前字符已在子串中出现，停止扩展
    • 否则更新最大长度
  3. 返回最大长度。

举例：对于 s = "abcabcbb"：

  • startIndex=0：子串 "ab" → "abc" → 遇到 a 重复，长度 3
  • startIndex=1：子串 "bc" → "bca" → 遇到 b 重复，长度 3
  • startIndex=2：子串 "ca" → "cab" → 遇到 c 重复，长度 3
  • …
  • 最长无重复子串长度为 3

复杂度分析

  • 时间复杂度：O(n^3)，两层循环加上 Contains 操作。
  • 空间复杂度：O(n)，存储子串的临时变量。

代码

// 方法一：双循环法
// 用两层循环，外层循环遍历字符串的每个字符作为子串的起始位置，内层循环遍历以当前字符为起始的所有子串，判断是否包含重复字符，从而找到最长的不含重复字符的子串。
static int LengthOfLongestSubstring1(string s)
{
    // 如果输入字符串为空，直接返回0
    if (s.Length == 0)
    {
        return 0;
    }

    // 如果输入字符串长度为1，直接返回1
    if (s.Length == 1)
    {
        return 1;
    }

    // 初始化最大长度和对应的子串
    int maxNum = 1; //至少有1个元素的话 子串至少都为1 所以初始化为1
    string resultString = "";

    // 外层循环，遍历所有可能的起始位置
    for (int startIndex = 0; startIndex < s.Length; startIndex++)
    {
        // 临时变量，用于记录当前子串的长度
        int tempMaxNum = 0;

        // 内层循环，遍历以startIndex为起始位置的所有子串
        for (int endIndex = startIndex + 1; endIndex < s.Length; endIndex++)
        {
            // 判断子串中是否包含当前字符 如果有重复的了往后继续遍历肯定也重复 没有意义 跳出循环
            if (s.Substring(startIndex, endIndex - startIndex).Contains(s[endIndex]))
            {
                // 发现重复字符，结束内层循环
                break;
            }

            // 计算当前子串的长度
            tempMaxNum = endIndex - startIndex + 1;

            // 如果当前临时最大长度大于全局最大长度，更新全局最大长度和对应子串
            if (tempMaxNum > maxNum)
            {
                maxNum = tempMaxNum;
                resultString = s.Substring(startIndex, endIndex - startIndex + 1);
            }
        }
    }

    //如果最长子串长度还是1 直接返回第一个元素算了
    if (maxNum == 1)
    {
        resultString = s[0].ToString();
    }

    // 输出最长子串
    Console.WriteLine(resultString);

    // 返回最大长度
    return maxNum;
}

方法二：滑动窗口单循环缓存字典法

思路

使用滑动窗口维护一个不含重复字符的子串。用字典记录每个字符的最新位置，当遇到重复字符时，将窗口起点跳转到重复字符的下一个位置。关键点：起点只能向后移动，不能回退。

核心思想：滑动窗口 + 字典记录位置，一次遍历完成。

具体步骤：

  1. 初始化窗口起点 startIndex = 0，字典 charIndexDictionary。
  2. 遍历字符串，对于每个字符 s[endIndex]：
    • 如果字符在字典中且位置 >= startIndex：更新 startIndex 为字典中位置 + 1
    • 更新字典中该字符的位置为当前索引
    • 更新最大长度
  3. 返回最大长度。

举例：对于 s = "abcabcbb"：

  • end=0, char='a'：字典 {a:0}，长度 1
  • end=1, char='b'：字典 {a:0, b:1}，长度 2
  • end=2, char='c'：字典 {a:0, b:1, c:2}，长度 3
  • end=3, char='a'：a 在字典中位置 0 >= 0，startIndex = 1，字典 {a:3, b:1, c:2}，长度 3
  • end=4, char='b'：b 在字典中位置 1 >= 1，startIndex = 2，字典 {a:3, b:4, c:2}，长度 3
  • end=5, char='c'：c 在字典中位置 2 >= 2，startIndex = 3，字典 {a:3, b:4, c:5}，长度 3
  • end=6, char='b'：b 在字典中位置 4 >= 3，startIndex = 5，字典 {a:3, b:6, c:5}，长度 2
  • end=7, char='b'：b 在字典中位置 6 >= 5，startIndex = 7，字典 {a:3, b:7, c:5}，长度 1
  • 最大长度为 3

复杂度分析

  • 时间复杂度：O(n)，只需遍历一次字符串。
  • 空间复杂度：O(min(m, n))，其中 m 是字符集大小。

代码

// 方法二：滑动窗口单循环缓存字典法
// 使用滑动窗口的思想，维护两个指针startIndex和endIndex，以及一个字典charIndexDictionary来存储字符及其在字符串中的最新索引。
// 通过单循环遍历字符串，判断是否有重复字符，从而找到最长的不含重复字符的子串。
// 每次发现重复元素后，开始位置的变化规律是变为前方重复元素的后一位（关键规律）。注意其实位置不能往前走只能往后走，往后走要特殊处理。 
static int LengthOfLongestSubstring2(string s)
{
    // 如果输入字符串为空或为null，直接返回0
    if (string.IsNullOrEmpty(s))
    {
        return 0;
    }

    // 如果输入字符串长度为1，直接返回1
    if (s.Length == 1)
    {
        return 1;
    }

    string resultString = "";

    // 初始化最大长度和起始位置
    int maxNum = 0;
    int startIndex = 0;

    // 创建一个字典，用于记录字符及其在字符串中的索引
    Dictionary<char, int> charIndexDictionary = new Dictionary<char, int>();

    // 遍历字符串中的每个字符
    for (int endIndex = 0; endIndex < s.Length; endIndex++)
    {
        // 如果当前字符在字典中存在，且其索引大于等于起始位置，要保证起始位置不能往回头
        if (charIndexDictionary.ContainsKey(s[endIndex]) && charIndexDictionary[s[endIndex]] >= startIndex)
        {
            // 每次发现重复元素后，startIndex的变化规律是变为前方重复元素的后一位（关键规律）
            // 如果是，更新起始位置为重复字符的下一个位置
            startIndex = charIndexDictionary[s[endIndex]] + 1;
        }

        // 更新字典中字符的索引为当前位置
        charIndexDictionary[s[endIndex]] = endIndex;

        if (endIndex - startIndex + 1 > maxNum)
        {
            resultString = s.Substring(startIndex, endIndex - startIndex + 1);
        }

        // 计算当前不含重复字符的子串长度，并更新最大长度
        maxNum = Math.Max(maxNum, endIndex - startIndex + 1);
    }

    // 输出最长子串
    Console.WriteLine(resultString);

    // 返回最大长度
    return maxNum;
}

3.3 代码

class Program
{
    static void Main()
    {
        #region 题目

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

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

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

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

        // 提示：
        // 0 <= s.length <= 5 * 104
        // s 由英文字母、数字、符号和空格组成

        #endregion

        #region 测试

        // 示例 1
        string s1 = "abcabcbb";
        int result11 = LengthOfLongestSubstring1(s1);
        Console.WriteLine($"示例1 方法1 输出：{result11}");
        int result12 = LengthOfLongestSubstring2(s1);
        Console.WriteLine($"示例1 方法2 输出：{result12}");

        // 示例 2
        string s2 = "bbbbb";
        int result21 = LengthOfLongestSubstring1(s2);
        Console.WriteLine($"示例2 方法1 输出：{result21}");
        int result22 = LengthOfLongestSubstring2(s2);
        Console.WriteLine($"示例2 方法2 输出：{result22}");

        // 示例 3
        string s3 = "pwwkew";
        int result31 = LengthOfLongestSubstring1(s3);
        Console.WriteLine($"示例3 方法1 输出：{result31}");
        int result32 = LengthOfLongestSubstring2(s3);
        Console.WriteLine($"示例3 方法2 输出：{result32}");

        #endregion
    }

    #region 答案

    // 方法一：双循环法
    // 用两层循环，外层循环遍历字符串的每个字符作为子串的起始位置，内层循环遍历以当前字符为起始的所有子串，判断是否包含重复字符，从而找到最长的不含重复字符的子串。
    static int LengthOfLongestSubstring1(string s)
    {
        // 如果输入字符串为空，直接返回0
        if (s.Length == 0)
        {
            return 0;
        }

        // 如果输入字符串长度为1，直接返回1
        if (s.Length == 1)
        {
            return 1;
        }

        // 初始化最大长度和对应的子串
        int maxNum = 1; //至少有1个元素的话 子串至少都为1 所以初始化为1
        string resultString = "";

        // 外层循环，遍历所有可能的起始位置
        for (int startIndex = 0; startIndex < s.Length; startIndex++)
        {
            // 临时变量，用于记录当前子串的长度
            int tempMaxNum = 0;

            // 内层循环，遍历以startIndex为起始位置的所有子串
            for (int endIndex = startIndex + 1; endIndex < s.Length; endIndex++)
            {
                // 判断子串中是否包含当前字符 如果有重复的了往后继续遍历肯定也重复 没有意义 跳出循环
                if (s.Substring(startIndex, endIndex - startIndex).Contains(s[endIndex]))
                {
                    // 发现重复字符，结束内层循环
                    break;
                }

                // 计算当前子串的长度
                tempMaxNum = endIndex - startIndex + 1;

                // 如果当前临时最大长度大于全局最大长度，更新全局最大长度和对应子串
                if (tempMaxNum > maxNum)
                {
                    maxNum = tempMaxNum;
                    resultString = s.Substring(startIndex, endIndex - startIndex + 1);
                }
            }
        }

        //如果最长子串长度还是1 直接返回第一个元素算了
        if (maxNum == 1)
        {
            resultString = s[0].ToString();
        }

        // 输出最长子串
        Console.WriteLine(resultString);

        // 返回最大长度
        return maxNum;
    }

    // 方法二：滑动窗口单循环缓存字典法
    // 使用滑动窗口的思想，维护两个指针startIndex和endIndex，以及一个字典charIndexDictionary来存储字符及其在字符串中的最新索引。
    // 通过单循环遍历字符串，判断是否有重复字符，从而找到最长的不含重复字符的子串。
    // 每次发现重复元素后，开始位置的变化规律是变为前方重复元素的后一位（关键规律）。注意其实位置不能往前走只能往后走，往后走要特殊处理。 
    static int LengthOfLongestSubstring2(string s)
    {
        // 如果输入字符串为空或为null，直接返回0
        if (string.IsNullOrEmpty(s))
        {
            return 0;
        }

        // 如果输入字符串长度为1，直接返回1
        if (s.Length == 1)
        {
            return 1;
        }

        string resultString = "";

        // 初始化最大长度和起始位置
        int maxNum = 0;
        int startIndex = 0;

        // 创建一个字典，用于记录字符及其在字符串中的索引
        Dictionary<char, int> charIndexDictionary = new Dictionary<char, int>();

        // 遍历字符串中的每个字符
        for (int endIndex = 0; endIndex < s.Length; endIndex++)
        {
            // 如果当前字符在字典中存在，且其索引大于等于起始位置，要保证起始位置不能王回头
            if (charIndexDictionary.ContainsKey(s[endIndex]) && charIndexDictionary[s[endIndex]] >= startIndex)
            {
                // 每次发现重复元素后，startIndex的变化规律是变为前方重复元素的后一位（关键规律）
                // 如果是，更新起始位置为重复字符的下一个位置
                startIndex = charIndexDictionary[s[endIndex]] + 1;
            }

            // 更新字典中字符的索引为当前位置
            charIndexDictionary[s[endIndex]] = endIndex;

            if (endIndex - startIndex + 1 > maxNum)
            {
                resultString = s.Substring(startIndex, endIndex - startIndex + 1);
            }

            // 计算当前不含重复字符的子串长度，并更新最大长度
            maxNum = Math.Max(maxNum, endIndex - startIndex + 1);
        }

        // 输出最长子串
        Console.WriteLine(resultString);

        // 返回最大长度
        return maxNum;
    }

    #endregion
}

3.4 运行结果

abc
示例1 方法1 输出：3
abc
示例1 方法2 输出：3
b
示例2 方法1 输出：1
b
示例2 方法2 输出：1
wke
示例3 方法1 输出：3
wke
示例3 方法2 输出：3
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏