求解最长无重复子串长度：滑动窗口算法的时间复杂度分析与优化-js教程-PHP中文网

求解最长无重复子串长度：滑动窗口算法的时间复杂度分析与优化

碧海醫心

发布： 2025-08-17 16:50:01

原创

832人浏览过

求解最长无重复子串长度：滑动窗口算法的时间复杂度分析与优化

本文旨在深入解析求解字符串中最长无重复子串长度的滑动窗口算法。我们将分析一种常见的实现方式，指出其潜在的时间复杂度问题，并提供一种更优的、时间复杂度为 O(n) 的解决方案。通过代码示例和详细解释，帮助读者理解算法原理并掌握优化技巧。

问题描述

给定一个字符串，找出其中最长且不包含重复字符的子串的长度。例如：

输入 "abcabcbb"，答案是 3 (对应子串 "abc")
输入 "bbbbb"，答案是 1 (对应子串 "b")
输入 "pwwkew"，答案是 3 (对应子串 "wke")

初始方案分析

最初的解决方案采用滑动窗口的思想，使用一个对象 (storage.cache) 来缓存字符及其索引。虽然看起来像是滑动窗口，但由于在遇到重复字符时，存在一个内部循环，导致其时间复杂度并非严格的 O(n)。

以下是原始代码：

var lengthOfLongestSubstring = function(str) {
    // Create storage object for caching
    let storage = {
        longestSubStringLength: 0,
        longestSubString: 0,
        cache: {
            subString: ''
        }
    };
    // Loop through string
    for (let i = 0; i < str.length; i++) {
        let char = str[i];
        if (!storage.cache[char] && storage.cache[char] !== 0) {
            // If current letter is not in storage, add it and extend current substring
            storage.cache[char] = i;
            storage.cache.subString += char;
        } else {
            // If current letter is already in storage, start a new round
            let previousCache = storage.cache;
            storage.cache = {
                subString: ''
            };
            if (previousCache[char] + 1 !== i) { // If there are letters in-between
                storage.cache.subString = str.substring(previousCache[char] + 1, i);
                for (let j = previousCache[char]; j < i; j++) {
                    storage.cache[str[j]] = j;
                }
            }
            storage.cache[char] = i;
            storage.cache.subString += char;
        }
        // If current substring is the longest, update it in storage
        if (storage.cache.subString.length > storage.longestSubStringLength) {
            storage.longestSubStringLength = storage.cache.subString.length;
            storage.longestSubString = storage.cache.subString;
        }
    }
    return storage.longestSubStringLength;
};

登录后复制

问题在于 else 分支中的内部 for 循环：

for (let j = previousCache[char]; j < i; j++) {
    storage.cache[str[j]] = j;
}

登录后复制

这个循环在遇到重复字符时，会迭代更新 storage.cache 中位于重复字符之间的字符的索引。在最坏情况下，例如 "abcdefghabcdefgh"，这个内部循环可能会执行多次，导致整体时间复杂度高于 O(n)。更准确地说，其时间复杂度接近 O(n*m)，其中 m 是最长不重复子串的平均长度。

优化方案：O(n) 时间复杂度的滑动窗口

为了实现真正的 O(n) 时间复杂度，我们可以使用 Map 数据结构来存储字符及其索引。Map 提供了快速的查找和更新操作。

以下是优化后的代码：

百度GBI

百度GBI-你的大模型商业分析助手

104

查看详情

const lengthOfLongestSubstring = str => {
    let cnt = 0;
    let n = str.length;
    let answer = 0;
    let map = new Map(); // to store the strings and their length
    for (let start = 0, end = 0; end < n; end++) { // slide
      // move start if the character is already in the map
      if (map.has(str[end])) start = Math.max(map.get(str[end]), start);
      answer = Math.max(answer, end - start + 1); // longest string
      map.set(str[end], end + 1);
      cnt++
    }
    return [str, `lookups: ${cnt} lookups:`, "answer", answer];
  }
  ["abcabcbb", "bbbbb", "pwwkew", "abcdefghabcdefgh"].forEach(str => console.log(lengthOfLongestSubstring(str).join(" ")))

登录后复制

代码解释：

map: 使用 Map 来存储字符及其在字符串中的下一个位置（索引 + 1）。
start 和 end: start 指向当前无重复子串的起始位置，end 指向当前遍历的字符。
滑动窗口: end 指针不断向右移动，扩展窗口。
重复字符处理: 如果 map 中已经存在当前字符 str[end]，则将 start 指针移动到 map.get(str[end]) 和当前 start 的较大值处。这是关键步骤，确保 start 始终指向当前无重复子串的有效起始位置。Math.max 的使用是为了避免 start 指针回退，这种情况可能发生在字符串中字符重复出现多次，且重复字符的索引小于当前的 start 值。
更新最大长度: 每次迭代都更新 answer，即最长无重复子串的长度。
更新 map: 将当前字符 str[end] 及其下一个位置 end + 1 存入 map。