登录
首页 >  文章 >  前端

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

时间:2025-08-22 15:06:34 270浏览 收藏

本文深入解析了使用滑动窗口算法求解“最长无重复子串”这一经典字符串问题。针对寻找字符串中最长且不包含重复字符的子串,文章详细阐述了滑动窗口算法的原理和实现,并对比分析了常见解法的时间复杂度。通过高效且易于理解的 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学习网公众号,给大家分享更多文章知识!

相关阅读
更多>
最新阅读
更多>
课程推荐
更多>