如何优化Scala实现的Minimum Window Substring滑动窗口解决方案？

API 探路者

2026-7-25

优化LeetCode最小覆盖子串的Scala滑动窗口实现

我用滑动窗口算法解决LeetCode上的**最小覆盖子串（Minimum Window Substring）**问题，题目标注为hard难度。核心思路是遍历字符串s的每个right索引，当窗口s.slice(left, right + 1)包含t的所有字符时，移动left索引缩小窗口，同时记录最小的有效窗口。

我最初用Scala的s.indices.foldLeft遍历right，嵌套尾递归移动left实现了逻辑，代码能通过测试，但性能仅击败20%的提交；改用命令式写法后性能提升有限，仅到30%。以下是初始实现代码：

def minWindow(s: String, t: String): String = {

  // all chars of "t"; maps each char to its count in "t"
  val map = t.groupBy(identity).map { case (k, v) => k -> v.length }

  case class Acc(winMap: Map[Char, Int], window: String, left: Int)
  s.indices.foldLeft(Acc(Map(), "", 0)) { case (acc, right) =>

    val winMap = acc.winMap.updated(s(right), acc.winMap.getOrElse(s(right), 0) + 1)

    def moveLeft(acc: Acc): Acc = {
      val isGood = map.forall { case (k, v) => acc.winMap.get(k).exists(_ >= v) }
      if (isGood) { // the window contains all chars of "t"
        val winMap = acc.winMap.updated(s(acc.left), acc.winMap(s(acc.left)) - 1)
        val window = if (acc.window.isEmpty || acc.window.length > right - acc.left + 1)
          s.slice(acc.left, right + 1)
        else acc.window
        moveLeft(Acc(winMap, window, acc.left + 1))
      } else acc
    }
    moveLeft(acc.copy(winMap = winMap))

  }.window
}

优化方向与简化方案

1. 替换不可变Map为可变哈希表

Scala的不可变Map每次updated都会生成新对象，带来大量内存开销和GC压力。改用java.util.HashMap（若字符范围是ASCII，用数组效率更高），直接修改计数，避免不必要的对象创建。

2. 优化窗口有效性检查逻辑

初始实现每次检查窗口是否有效都要遍历t的所有字符（map.forall），时间复杂度为O(k)（k是t的不同字符数）。改为维护一个formed计数器：每有一个字符的窗口计数达到t中的要求，formed加1；当formed等于t的不同字符数时，窗口有效。这个检查变成O(1)操作。

3. 避免频繁字符串切片

每次调用s.slice都会生成新字符串，改为记录最小窗口的起始和结束索引，最后仅在需要时截取一次结果，减少内存分配。

4. 用循环替代foldLeft和尾递归

虽然Scala尾递归会被优化为循环，但直接用while循环更贴合滑动窗口的执行逻辑，减少函数调用的额外开销，代码也更直观。

优化后的代码实现

import java.util.HashMap

def minWindow(s: String, t: String): String = {
  if (s.isEmpty || t.isEmpty) return ""

  // 统计t中各字符的出现次数
  val tCharCount = new HashMap[Char, Int]()
  t.foreach(c => tCharCount.put(c, tCharCount.getOrDefault(c, 0) + 1))
  val requiredUniqueChars = tCharCount.size()

  var left = 0
  var right = 0
  var formedValidChars = 0 // 满足t中数量要求的字符种类数
  val windowCharCount = new HashMap[Char, Int]()

  // 记录最小窗口的信息：长度、起始索引、结束索引
  var minWindowLen = Int.MaxValue
  var minStart = 0
  var minEnd = 0

  while (right < s.length) {
    val currentChar = s(right)
    // 更新窗口内当前字符的计数
    val currentCount = windowCharCount.getOrDefault(currentChar, 0) + 1
    windowCharCount.put(currentChar, currentCount)

    // 如果当前字符的计数达到t中的要求，更新有效字符种类数
    if (tCharCount.containsKey(currentChar) && currentCount == tCharCount.get(currentChar)) {
      formedValidChars += 1
    }

    // 当窗口有效时，尝试移动left缩小窗口
    while (left <= right && formedValidChars == requiredUniqueChars) {
      val leftChar = s(left)
      // 更新最小窗口记录
      val currentWindowLen = right - left + 1
      if (currentWindowLen < minWindowLen) {
        minWindowLen = currentWindowLen
        minStart = left
        minEnd = right
      }

      // 移出left位置的字符，更新计数
      windowCharCount.put(leftChar, windowCharCount.get(leftChar) - 1)
      if (tCharCount.containsKey(leftChar) && windowCharCount.get(leftChar) < tCharCount.get(leftChar)) {
        formedValidChars -= 1
      }

      left += 1
    }

    right += 1
  }

  // 返回结果：如果没找到有效窗口返回空串，否则截取最小窗口
  if (minWindowLen == Int.MaxValue) "" else s.substring(minStart, minEnd + 1)
}

优化效果说明

哈希表的直接修改减少了对象创建开销，提升内存效率；
formedValidChars计数器将窗口检查从O(k)降为O(1)，大幅降低时间复杂度；
延迟字符串截取减少了内存分配次数；
循环逻辑更高效，避免了函数调用的额外开销，性能可提升至击败90%以上的提交。

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