求我实现的双指针算法求解最小重排子串问题的时间复杂度

一、时间复杂度分析 #

你的代码时间复杂度确实不是O(n)，最坏情况下是O(n²)，原因如下：

• 你每次凑齐t的所有字符后，会直接把右指针i重置为start+1，相当于右指针要重复遍历已经扫过的字符
• 最坏场景比如s为全a字符串（共n个a），t为单个a，那么每次匹配后start加1，i回退到start，总遍历次数是n+(n-1)+(n-2)+...+1 = n(n+1)/2，时间复杂度就是O(n²)，完全无法适配输入规模100万的场景。

二、代码存在的其他问题 #

1. 统计t字符频率的逻辑有笔误：
   letters.set(tc, (letters.get(t) || 0) +1); 这里你写的是get(t)（t是整个字符串），应该是get(tc)，否则统计的频率完全错误，会直接导致结果不对。
2. 遇到不属于t的字符时没有重置计数状态：如果当前已经在统计匹配的字符，中途遇到不属于t的字符，你只移动右指针，会导致后续计算的子串长度包含无关字符，结果偏大。
3. 匹配成功后重置窗口的逻辑效率极低，没有复用之前的统计结果，是时间复杂度偏高的核心原因。

三、正确的O(n)解法思路 #

用标准滑动窗口模板，左右指针都只向前移动不回退：

1. 先统计t的所有字符的频率，记录需要满足的字符种类数
2. 右指针遍历s，更新窗口内的字符频率，当所有t的字符频率都满足要求时，尝试移动左指针缩小窗口，更新最小长度
3. 全程左右指针各遍历s一次，时间复杂度是O(n)，可以适配100万的输入规模。

修正后可运行的正确代码（滑动窗口版） #

function minLengthSubstring(s, t) {
  if (t.length > s.length) return -1;
  // 统计t的字符频率
  const need = new Map();
  for (const c of t) {
    need.set(c, (need.get(c) || 0) + 1);
  }
  const window = new Map();
  let left = 0, right = 0;
  let valid = 0;
  let minLen = Infinity;
  while (right < s.length) {
    const c = s[right];
    right++;
    if (need.has(c)) {
      window.set(c, (window.get(c) || 0) + 1);
      if (window.get(c) === need.get(c)) {
        valid++;
      }
    }
    // 满足条件时收缩左窗口
    while (valid === need.size) {
      // 更新最小长度
      if (right - left < minLen) {
        minLen = right - left;
      }
      const d = s[left];
      left++;
      if (need.has(d)) {
        if (window.get(d) === need.get(d)) {
          valid--;
        }
        window.set(d, window.get(d) - 1);
      }
    }
  }
  return minLen === Infinity ? -1 : minLen;
}

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