统计含恰好K个唯一字符子串的时间与空间复杂度分析

我正在研究一道LeetCode面试题的解决方案，代码如下：

function SubstringsKDistinct(str, k) {
    let start = 0;
    let end = 0;
    let result = [];
    let len = str.length;

    while (start < len && end < len) {
        while (end <= len) {
            if (str.slice(start, end).length > 1) {
                let set = new Set(str.slice(start, end));
                if (set.size == k) {
                    result.push(str.slice(start, end));
                }
            }
            end++;
        }
        start++;
        end = start;
    }
    return result.length;
}

我的初步分析：时间复杂度为O(N²)，因为内外层while循环的操作次数都受输入字符串长度限制；空间复杂度为O(N)，因为结果数组的大小取决于输入串长度。想确认这个分析是否正确，并学习面试中这类操作的复杂度分析方法。

复杂度分析修正与验证 #

你的初步分析存在不准确的地方，具体拆解如下：

1. 时间复杂度

外层循环start从0到N-1，共执行N次；内层循环end从start到N，每次内层循环最多执行N-start次，循环总迭代次数确实是O(N²)。但循环内部的操作并非O(1)：

• str.slice(start, end)会创建新子串，时间复杂度为O(end-start)（即子串长度L）
• 用子串初始化Set需要遍历每个字符，时间同样是O(L)

所有子串的总长度为O(N²)（长度为N的字符串，所有子串总长度为N*(N+1)/2），因此整体时间复杂度应为O(N³)，远高于你最初判断的O(N²)。

2. 空间复杂度

• 若统计输出空间：最坏情况下（如字符串所有字符不同，k=2），符合条件的子串数量是O(N²)，每个子串最长为N，因此结果数组的空间复杂度为O(N³)
• 若仅统计辅助空间（除输入、输出外的额外空间）：Set的最大大小为N（极端子串包含所有不同字符），因此辅助空间复杂度为O(N)

面试中复杂度分析的实用方法 #

• 拆解循环结构：先统计各层循环的执行次数，比如双层循环的总迭代次数通常是O(N²)，注意循环变量的步长（若每次跳固定步数，次数会成比例减少）。
• 深挖循环内操作：不要默认循环内是O(1)操作，像str.slice、Set初始化这类需要遍历元素的操作，要把它们的时间成本算入总复杂度。
• 区分复杂度场景：面试中优先说最坏情况复杂度，同时可补充平均/最好情况（比如这道题k=1且字符串全相同时，时间复杂度会降到O(N²)）。
• 明确空间统计范围：分清楚「辅助空间」（除输入、输出外的额外空间）和「输出空间」（题目要求返回的结果占用空间），面试时按需说明。
• 结合优化思路验证：比如这道题可以用滑动窗口+哈希表优化到O(N)时间，对比原代码的复杂度，能更清晰地看出原实现的低效点。

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