求lengthOfLongestSubstring实现代码的时间复杂度分析

这是LeetCode的经典题目：函数接收字符串输入，返回最长无重复字符子串的长度，示例如下：

• 输入abcabcbb返回3，对应子串abc
• 输入bbbbb返回1，对应子串b
• 输入pwwkew返回3，对应子串wke

该问题的最优解法是滑动窗口技术，时间复杂度为O(n)。但以下实现属于类滑动窗口思路，因包含触发式内层循环，达不到O(n)复杂度，且该内层循环完全冗余。

代码逻辑与循环分析 #

代码采用嵌套循环结构：

• 外层循环遍历输入字符串的每个字符，共执行n次（n为字符串长度）。
• 每次遇到重复字符时，触发内层循环，循环次数等于当前字符与上一次出现位置之间的字符数量。

举几个具体例子：

• 输入abcabcbb：外层循环执行8次；遇到第二个a时内层循环执行3次（遍历索引0、1、2的字符）；遇到第二个b时内层循环执行3次（遍历索引1、2、3的字符）；遇到第二个c时内层循环执行3次（遍历索引2、3、4的字符）；遇到倒数第二个b时内层循环执行1次（遍历索引6的字符）；最后一个b无中间字符，不触发内层循环。
• 最坏情况示例：输入为abcdefgh重复两次（总长度16），外层循环执行16次；遇到重复字符时触发8次内层循环，每次执行8次迭代（遍历前一段的8个字符）。

推广到一般场景：假设原串包含m个唯一字符，重复多次后总长度为n：

• 外层循环执行n次
• 内层循环总次数约为(n - m) * m（每次触发内层循环处理m个字符，共触发约n/m次）
• 总操作数为外层循环次数加内层循环总次数

时间复杂度结论 #

时间复杂度的大O表示只保留最高阶项、忽略常数与低阶项：

• 当m（唯一字符数）接近n/2时，内层循环总次数约为n²/4，此时总操作数的最高阶项为n²，因此最坏时间复杂度为O(n²)。
• 若m为固定常数（如输入仅包含ASCII字符，m≤128），内层循环总次数为O(n)，此时总时间复杂度为O(n)。

但算法复杂度分析通常以最坏情况为准，因此该代码的时间复杂度为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;
};

内容的提问来源于stack exchange，提问作者89Tr34Ve