DEV Community
·
Leetcode 3. 最长无重复字符子串
💡
原文英文，约500词，阅读约需2分钟。
📝
内容提要
给定字符串s，使用哈希表记录字符索引，采用双指针方法找出最长无重复字符子串的长度，时间复杂度为O(n)，空间复杂度为O(256)。
🎯
关键要点
-
给定字符串s，找出最长无重复字符子串的长度。
-
示例1：输入为 'abcabcbb'，输出为3，最长子串为 'abc'。
-
示例2：输入为 'bbbbb'，输出为1，最长子串为 'b'。
-
示例3：输入为 'pwwkew'，输出为3，最长子串为 'wke'。
-
需要考虑所有子串，检查是否有重复字符，避免使用O(N^2)复杂度的双重循环。
-
使用哈希表记录字符索引，判断字符是否在当前窗口内。
-
创建大小为256的哈希数组，维护两个指针和最大长度。
-
遍历字符串，检查当前字符是否已见，更新最大长度和哈希表。
-
时间复杂度为O(n)，空间复杂度为O(256)。
❓
延伸问答
如何找到字符串中最长无重复字符的子串长度？
使用哈希表记录字符索引，采用双指针方法遍历字符串，更新最大长度。
给定字符串 'abcabcbb'，最长无重复字符子串是什么？
最长无重复字符子串是 'abc'，长度为3。
该算法的时间复杂度和空间复杂度分别是多少？
时间复杂度为O(n)，空间复杂度为O(256)。
如何处理重复字符以避免O(N^2)复杂度？
通过哈希表记录字符索引，移动左指针以跳过重复字符，从而避免双重循环。
在字符串 'pwwkew' 中，最长无重复字符子串是什么？
最长无重复字符子串是 'wke'，长度为3。
如何初始化哈希表以存储字符索引？
创建大小为256的哈希数组，并将所有元素初始化为-1。
➡️
