滑动窗口解最长不重复子串时间复杂度

本文深入探讨了使用滑动窗口算法求解字符串最长无重复子串长度的问题，并针对常见实现方式中存在的时间复杂度问题进行了分析。最初的方案虽然使用了滑动窗口，但由于内部循环的存在，导致时间复杂度并非严格的O(n)。为了优化算法性能，本文提出了一种基于Map数据结构的改进方案，将时间复杂度降低到O(n)。通过代码示例和详细的步骤解释，本文旨在帮助读者理解滑动窗口算法的原理，并掌握优化技巧，从而高效解决字符串处理中的相关问题。该优化后的算法在处理大规模字符串时具有显著优势。

本文旨在深入解析求解字符串中最长无重复子串长度的滑动窗口算法。我们将分析一种常见的实现方式，指出其潜在的时间复杂度问题，并提供一种更优的、时间复杂度为 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 提供了快速的查找和更新操作。

以下是优化后的代码：

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(" ")))

代码解释：

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

时间复杂度分析：

• 外层循环 for (let start = 0, end = 0; end < n; end++) 遍历字符串一次，O(n)。
• Map 的 has、get 和 set 操作的平均时间复杂度为 O(1)。

因此，整体时间复杂度为 O(n)。

空间复杂度分析：

空间复杂度为 O(min(m, n))，其中 m 是字符集的大小，n 是字符串的长度。这是因为 Map 最多存储 m 个不同的字符及其索引。

总结

通过使用 Map 数据结构和滑动窗口技术，我们可以高效地解决最长无重复子串问题，并将时间复杂度优化到 O(n)。 关键在于正确地维护滑动窗口的起始位置，并利用 Map 快速查找和更新字符的索引。 这种方法不仅提高了效率，还使代码更简洁易懂。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《滑动窗口解最长不重复子串时间复杂度》文章吧，也可关注golang学习网公众号了解相关技术文章。