leetcode3. 无重复字符的最长子串，哈希表

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

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

子串：连续

题目分析

我们需要找到字符串中最长的不含有重复字符的子串的长度。可以使用滑动窗口的方法，通过维护一个无重复字符的窗口，来找到最长的子串。

总体思维导图

算法步骤

1. 初始化一个空的哈希集合 st 和两个指针 l 和 i，分别表示滑动窗口的左边界和当前遍历的字符位置。
2. 遍历字符串 s 中的每个字符。
3. 如果当前字符不在哈希集合中，则将其加入集合，并更新最长子串长度。
4. 如果当前字符在哈希集合中，则移动左指针 l，直到窗口中不包含当前字符，然后更新最长子串长度。
5. 返回最长子串长度。

具体流程

具体代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<int> st;
        int l=0;
        int res=0;
        for(int i=0;i<s.size();i++)
        {
            if(st.find(s[i])==st.end())
            {
                st.insert(s[i]);
                res=max(res,i-l+1);
            }
            else
            {
                while(st.find(s[i])!=st.end())
                {
                    st.erase(s[l]);
                    l++;
                }
                st.insert(s[i]);
                res=max(res,i-l+1);
            }
        }
        return res;
    }
};

算法分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。每个字符最多被遍历两次。
• 空间复杂度：O(min(m, n))，其中 m 是字符集的大小，n 是字符串 s 的长度。哈希集合的大小最多为 min(m, n)。

易错点和注意事项

• 注意哈希集合中存储的是字符的 ASCII 码值，而不是字符本身。
• 在更新最长子串长度时，要使用 max 函数来确保 res 是递增的。
• 在移动左指针时，要确保窗口中不包含当前字符，才能将当前字符加入哈希集合。

相似题目

题目	链接
无重复字符的最长子串	https://leetcode.cn/problems/longest-substring-without-repeating-characters/
最长回文子串	https://leetcode.cn/problems/longest-palindromic-substring/
最小覆盖子串	https://leetcode.cn/problems/minimum-window-substring/

原文地址：https://blog.csdn.net/qq_51350957/article/details/145238080

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！