求解最长无重复子串长度：滑动窗口算法详解-小浪学习网

求解最长无重复子串长度：滑动窗口算法详解

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

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

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

算法思路

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

具体步骤如下：

初始化： 定义两个指针 start 和 end，分别指向窗口的起始位置和结束位置。初始时，start 和 end 都指向字符串的第一个字符。同时，使用一个 map 数据结构（或其他合适的哈希表）来记录窗口内每个字符的最新位置。
滑动窗口： end 指针不断向右移动，将新的字符加入窗口。
检查重复： 每当 end 指针指向一个新的字符时，检查该字符是否已经在窗口中出现过（即，是否在 Map 中存在）。
- 如果字符未出现过： 将该字符及其位置加入 Map，并更新最长无重复子串的长度。
- 如果字符已经出现过： 说明当前窗口内出现了重复字符，需要调整窗口的起始位置 start。将 start 指针移动到重复字符上次出现的位置之后（即 Map.get(str[end])）。同时，更新 start 指针时，需要确保 start 指针不会倒退，因此需要使用 math.max(map.get(str[end]), start) 来确保 start 指针始终保持在当前位置或更靠右的位置。
更新最长长度： 在每次滑动窗口后，都需要更新最长无重复子串的长度。
循环： 重复步骤 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 中。