如何优化LeetCode Ransom Note的Scala解法以提升运行速度？

你的解法逻辑完全正确，但groupBy的使用会带来额外的性能开销——构建和操作Map的成本比直接用数组统计字符频率要高不少，而且没法提前终止判断。下面是几个能明显提升运行速度的优化方向：

1. 用数组替代Map统计字符频率 #

因为题目中涉及的字符都是小写英文字母（LeetCode该题的默认约束），我们可以用一个长度为26的数组来统计每个字母的出现次数。数组的访问速度远快于Map，而且内存占用更小。

同时，我们可以在遍历ransomNote时提前终止判断：一旦发现某个字符的剩余数量不足，直接返回false，避免遍历完整个字符串。

优化后的代码：

def canConstruct(ransomNote: String, magazine: String): Boolean = {
  val count = new Array[Int](26)
  // 统计magazine中每个字符的出现次数
  magazine.foreach(c => count(c - 'a') += 1)
  
  // 检查ransomNote的每个字符是否足够
  ransomNote.foreach { c =>
    val idx = c - 'a'
    count(idx) -= 1
    if (count(idx) < 0) return false
  }
  
  true
}

2. 提前过滤长度不满足的情况 #

如果ransomNote的长度本身就大于magazine，那无论如何都不可能构造出ransomNote，直接返回false即可，这能快速过滤掉大量无效用例。

整合后的最终版本：

def canConstruct(ransomNote: String, magazine: String): Boolean = {
  // 提前判断长度，快速返回不可能的情况
  if (ransomNote.length > magazine.length) return false
  
  val count = new Array[Int](26)
  magazine.foreach(c => count(c - 'a') += 1)
  
  ransomNote.foreach { c =>
    val idx = c - 'a'
    count(idx) -= 1
    if (count(idx) < 0) return false
  }
  
  true
}

3. 去掉不必要的Seq转换 #

你原解法中用了toSeq，但Scala的String本身就是可遍历的，直接调用foreach或者遍历即可，不需要额外转换为Seq，这能减少一点点不必要的开销。

这些优化后，你的代码运行速度应该会和其他高效的Scala提交持平——毕竟数组操作的时间复杂度是O(m + n)，而且没有额外的Map构建开销，还能提前终止，性能提升很明显。

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