滑动窗口解最长不重复子串

本文深入解析了使用滑动窗口算法求解“最长无重复子串”这一经典字符串问题。针对寻找字符串中最长且不包含重复字符的子串，文章详细阐述了滑动窗口算法的原理和实现，并对比分析了常见解法的时间复杂度。通过高效且易于理解的 JavaScript 代码示例，结合详细注释，读者可以快速掌握滑动窗口算法的核心思想。文章重点介绍了如何在O(n)的时间复杂度内，通过维护一个动态调整大小的窗口，利用 Map 数据结构记录字符位置，实现对最长无重复子串的查找和长度更新。本文旨在帮助读者灵活运用滑动窗口算法，解决类似的字符串处理问题，并提升编程能力。

本文深入探讨了求解字符串中最长无重复子串长度的经典问题，并重点分析了使用滑动窗口算法的实现。文章首先分析了常见解法的时间复杂度，并提供了一个高效且易于理解的 JavaScript 实现，结合示例代码和详细注释，帮助读者掌握滑动窗口算法的精髓，并能灵活应用于解决类似字符串处理问题。

滑动窗口算法：O(n) 时间复杂度的解决方案

经典的“最长无重复子串”问题，要求在一个字符串中找到最长的子串，该子串中不包含重复字符。一种高效的解决方案是使用滑动窗口算法，该算法可以在 O(n) 的时间复杂度内解决此问题，其中 n 是字符串的长度。

算法思路

滑动窗口算法的核心思想是维护一个窗口，该窗口在字符串上滑动，并在滑动过程中动态调整窗口的大小，以满足问题的约束条件（在本例中，约束条件是窗口内的字符不能重复）。

具体步骤如下：

1. 初始化： 定义两个指针 start 和 end，分别指向窗口的起始位置和结束位置。初始时，start 和 end 都指向字符串的第一个字符。同时，使用一个 Map 数据结构（或其他合适的哈希表）来记录窗口内每个字符的最新位置。

2. 滑动窗口： end 指针不断向右移动，将新的字符加入窗口。

3. 检查重复： 每当 end 指针指向一个新的字符时，检查该字符是否已经在窗口中出现过（即，是否在 Map 中存在）。

   • 如果字符未出现过： 将该字符及其位置加入 Map，并更新最长无重复子串的长度。
   • 如果字符已经出现过： 说明当前窗口内出现了重复字符，需要调整窗口的起始位置 start。将 start 指针移动到重复字符上次出现的位置之后（即 Map.get(str[end])）。同时，更新 start 指针时，需要确保 start 指针不会倒退，因此需要使用 Math.max(map.get(str[end]), start) 来确保 start 指针始终保持在当前位置或更靠右的位置。

4. 更新最长长度： 在每次滑动窗口后，都需要更新最长无重复子串的长度。

5. 循环： 重复步骤 2-4，直到 end 指针到达字符串的末尾。

JavaScript 代码示例

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 answer;
  }

  // 示例测试
  ["abcabcbb", "bbbbb", "pwwkew", "abcdefghabcdefgh"].forEach(str => console.log(str + ": " + lengthOfLongestSubstring(str)))

代码解释：

• map: 使用 Map 数据结构来存储字符及其在字符串中的索引。
• start 和 end: start 指针指向当前窗口的起始位置，end 指针指向当前窗口的结束位置。
• if (map.has(str[end])) start = Math.max(map.get(str[end]), start);: 如果当前字符 str[end] 已经在 map 中存在，则将 start 指针移动到 map.get(str[end]) 的位置，确保窗口内没有重复字符。使用 Math.max 避免 start 指针倒退。
• answer = Math.max(answer, end - start + 1);: 更新最长无重复子串的长度。
• map.set(str[end], end + 1);: 将当前字符 str[end] 及其索引 end + 1 存入 map 中。

时间和空间复杂度

• 时间复杂度： O(n)，因为 start 和 end 指针最多遍历字符串一次。
• 空间复杂度： O(min(m, n))，其中 m 是字符集的大小，n 是字符串的长度。空间复杂度取决于 Map 中存储的字符数量，最坏情况下，Map 需要存储整个字符串中的所有字符。

总结与注意事项

滑动窗口算法是一种解决字符串问题的有效方法，特别是在需要寻找满足特定约束条件的子串时。 理解滑动窗口的原理，并能够灵活运用，可以帮助我们解决许多类似的字符串处理问题。

注意事项：

• 在实现滑动窗口算法时，需要仔细考虑窗口的起始位置和结束位置的更新逻辑，确保窗口始终满足问题的约束条件。
• 根据具体问题的特点，选择合适的数据结构来存储窗口内的信息，例如 Map、Set 或数组。
• 注意处理边界情况，例如空字符串或字符串长度为 1 的情况。

通过本文的学习，相信你已经掌握了使用滑动窗口算法解决“最长无重复子串”问题的精髓。希望你能将这种思想应用到其他字符串处理问题中，并不断提升自己的编程能力。

好了，本文到此结束，带大家了解了《滑动窗口解最长不重复子串》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！