本文旨在深入解析求解字符串中最长无重复子串长度的滑动窗口算法。我们将分析一种常见的实现方式，指出其潜在的时间复杂度问题，并提供一种更优的、时间复杂度为 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(" ")))
代码解释：
- 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。
时间复杂度分析：
- 外层循环 for (let start = 0, end = 0; end
- Map 的 has、get 和 set 操作的平均时间复杂度为 O(1)。
因此，整体时间复杂度为 O(n)。
空间复杂度分析：
空间复杂度为 O(min(m, n))，其中 m 是字符集的大小，n 是字符串的长度。这是因为 Map 最多存储 m 个不同的字符及其索引。
总结
通过使用 Map 数据结构和滑动窗口技术，我们可以高效地解决最长无重复子串问题，并将时间复杂度优化到 O(n)。 关键在于正确地维护滑动窗口的起始位置，并利用 Map 快速查找和更新字符的索引。 这种方法不仅提高了效率，还使代码更简洁易懂。
评论（已关闭）
评论已关闭