寻找最长无重复字符子串：时间复杂度分析与优化-js教程-PHP中文网

寻找最长无重复字符子串：时间复杂度分析与优化

花韻仙語

发布： 2025-08-17 17:52:31

原创

872人浏览过

寻找最长无重复字符子串：时间复杂度分析与优化

本文旨在深入探讨寻找字符串中最长无重复字符子串问题的解法，重点分析滑动窗口算法的时间复杂度。通过对一种常见实现的剖析，揭示其潜在的 O(n^2) 时间复杂度，并提供优化后的 O(n) 解决方案，该方案利用 Map 数据结构提升效率和可读性。同时，我们还将讨论空间复杂度的影响因素，帮助读者全面理解算法性能。

在字符串处理中，寻找最长无重复字符子串是一个经典问题。常见的解法是使用滑动窗口技术。然而，即使采用了滑动窗口的思想，不同的实现方式也会导致不同的时间复杂度。本文将分析一种常见的滑动窗口实现，指出其潜在的性能瓶颈，并提供一种更优的解决方案。

问题描述

给定一个字符串，找到其中最长的不包含重复字符的子串的长度。

例如：

输入 "abcabcbb"，答案是 3，因为最长无重复子串是 "abc"。
输入 "bbbbb"，答案是 1，因为最长无重复子串是 "b"。
输入 "pwwkew"，答案是 3，因为最长无重复子串是 "wke"。注意，答案必须是子串，"pwke" 是子序列，不是子串。

常见实现的复杂度分析

以下代码展示了一种常见的滑动窗口实现：

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

登录后复制

这段代码虽然使用了滑动窗口的思想，但其时间复杂度并非 O(n)。主要问题在于内部的 for 循环：

for (let j = previousCache[char]; j < i; j++) {
    storage.cache[str[j]] = j;
}

登录后复制

当遇到重复字符时，这个循环会遍历之前子串中的一部分字符，更新它们在 storage.cache 中的索引。在最坏的情况下，例如输入 "abcdefghabcdefgh"，这个内部循环会被多次触发，导致时间复杂度上升到 O(n^2)。

具体来说，外层循环遍历字符串的每个字符，复杂度为 O(n)。内层循环的执行次数取决于重复字符之间的距离。在最坏情况下，内层循环的平均执行次数也可能接近 O(n)，因此总的时间复杂度为 O(n * n) = O(n^2)。

优化后的 O(n) 解决方案

为了将时间复杂度降低到 O(n)，可以使用 Map 数据结构来记录字符的索引，并避免内部循环。

Browse AI

AI驱动的网页内容抓取和数据采集工具

查看详情

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

登录后复制

这段代码使用 Map 来存储每个字符最后出现的位置。当遇到重复字符时，直接更新滑动窗口的起始位置 start，而不需要遍历之前的子串。

时间复杂度分析：