Matarialize中文社区-LeetCode 热题 100专栏

无重复字符的最长子串

哈希表,字符串,滑动窗口

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

解法一：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if (!s) {
        return 0;
    }
    if (s.length === 1) {
        return 1;
    }

    let set = new Set();
    let left = 0;
    let maxLength = 0;

    for (let i = 0; i < s.length; i++) {
        while (set.has(s[i])) {
            set.delete(s[left]);
            left++;
        }
        set.add(s[i]);
        maxLength = Math.max(maxLength, i - left + 1);
    }
    return maxLength;
};

要找到字符串 s 中不含重复字符的最长子串的长度，我们可以使用滑动窗口技术结合哈希表来实现。这种方法可以在一次遍历中解决问题，从而高效地找到最长的无重复字符子串。

方法：滑动窗口

算法步骤

初始化变量：

使用一个哈希集合 char_set 来存储当前窗口中不重复的字符。
使用两个指针 left 和 right 表示滑动窗口的左右边界，初始值为 0。
初始化 max_length 为 0，用于存储最长无重复字符子串的长度。

滑动窗口遍历字符串：

如果 s[right] 不在 char_set 中：
如果 s[right] 在 char_set 中：

将 s[right] 加入 char_set。
更新 max_length 为 max(max_length, right - left + 1)。

从 char_set 中移除 s[left]，并将 left 指针右移，直到 s[right] 不在 char_set 中。
使用 right 指针遍历字符串 s。
对于每个字符 s[right]，检查其是否在 char_set 中。
将当前字符 s[right] 加入 char_set，继续移动 right 指针。

返回结果：

遍历结束后，max_length 即为最长无重复字符子串的长度。

算法实现

下面是用 Python 实现的代码：

def length_of_longest_substring(s):
    char_set = set()
    left = 0
    max_length = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)

    return max_length

# 示例
s = "abcabcbb"
result = length_of_longest_substring(s)
print("最长无重复字符子串的长度:", result)

示例

输入：s = "abcabcbb"
输出：3

解释

在这个例子中，最长无重复字符子串为 "abc"，其长度为 3。

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 s 的长度。每个字符在滑动窗口的左右指针之间最多被访问两次。
空间复杂度：O(min(n, m))，其中 n 是字符串 s 的长度，m 是字符集的大小。使用哈希集合来存储字符。

这种方法通过滑动窗口有效地在 O(n) 时间内解决了最长无重复字符子串的问题，是解决此类问题的常用技巧。

评论区

字数统计

评论列表