LeetCode 挑战：3. 最长无重复字符子字符串 - JavaScript 解决方案

最长无重复字符子串问题是一个经典的滑动窗口问题，它测试您有效管理子串的能力。让我们一步一步解决 LeetCode 3。

问题描述

给定一个字符串s，返回最长不包含重复字符的子字符串的长度。

示例

示例 1

Input: s = "abcabcbb"  
Output: 3  
Explanation: The answer is "abc", with a length of 3.

示例 2

Input: s = "bbbbb"  
Output: 1  
Explanation: The answer is "b", with a length of 1.

示例 3

Input: s = "pwwkew"  
Output: 3  
Explanation: The answer is "wke", with a length of 3.

JavaScript 解决方案

我们将使用滑动窗口技术来跟踪当前子字符串和集合以确保没有重复的字符。

滑动窗口实现

var lengthOfLongestSubstring = function(s) {
    let maxLength = 0;
    let left = 0;
    const seen = new Set();

    for (let right = 0; right < s.length; right++) {
        while (seen.has(s[right])) {
            seen.delete(s[left]);
            left++;
        }

        seen.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
};

工作原理

1. 滑动窗口：
   

• 使用两个指针（left和right）来表示当前子字符串。

• 指针right通过包含字符来扩大窗口。

• 指针left缩小窗口以消除重复的字符。

1. 设置唯一性：
   

• 使用 aSet存储当前子字符串中的字符。

• 如果发现重复，则从中删除字符，left直到删除重复项。

1. 更新最大长度：
   

• 计算子串长度right - left + 1并更新maxLength。

复杂性分析

• 时间复杂度：O(n)，其中n是字符串的长度。
  

• 每个字符最多从集合中添加和删除一次。

• 空间复杂度：O(k)，其中k是字符集的大小（例如，小写英文字母为 26）。

试运行

输入： 输出：s = "abcabcbb"

3

替代方案：使用哈希图优化滑动窗口，
而不是使用Set，哈希图可以跟踪每个字符的最后一个索引。

优化实施

var lengthOfLongestSubstring = function(s) {
    let maxLength = 0;
    let left = 0;
    const charIndexMap = {};

    for (let right = 0; right < s.length; right++) {
        if (charIndexMap[s[right]] !== undefined && charIndexMap[s[right]] >= left) {
            left = charIndexMap[s[right]] + 1;
        }

        charIndexMap[s[right]] = right;
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
};

复杂度分析（优化版）

• 时间复杂度：O(n)，因为每个字符处理一次。

• 空间复杂度：O(k)，其中k是字符集的大小。

了解更多

在我之前的 Dev.to 帖子中查看完整的解释和代码演示：
最小子数组和- JavaScript 解决方案

您更喜欢哪种滑动窗口实现？下面让我们讨论一下！