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

LeetCode LeetCode 哈希表 字符串 滑动窗口
发布时间 :
字数:2.4k 阅读 : 评论:
  1. 3.无重复字符的最长子串
    1. 3.1 题目
    2. 3.2 题解
      1. 双循环法
      2. 滑动窗口单循环缓存字典法
    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 题解

双循环法

// 方法一：双循环法
// 用两层循环，外层循环遍历字符串的每个字符作为子串的起始位置，内层循环遍历以当前字符为起始的所有子串，判断是否包含重复字符，从而找到最长的不含重复字符的子串。
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;
}

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-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏