如何在保留顺序的前提下生成Scala队列的连续子序列？

首先，你的原实现存在两个核心问题：

1. 循环范围错误，会生成空字符串（当i >= j时）；
2. 每次调用slice(i,j)都会创建新的子集合，再通过mkString遍历拼接，时间复杂度达到O(n³)，效率极低。

优化方案一：使用StringBuilder逐步构建字符串 #

通过逐步追加元素的方式，避免重复创建子集合和重复遍历，将时间复杂度降至O(n²)：

import scala.collection.mutable.Queue

val q = Queue("golden", "lion", "and", "golden", "lady")

for (i <- q.indices) {
  // 初始化StringBuilder为当前起始元素
  val sb = new StringBuilder(q(i))
  println(sb.toString())
  // 从起始位置的下一个元素开始，逐步追加
  for (j <- i + 1 until q.length) {
    sb.append(" ").append(q(j))
    println(sb.toString())
  }
}

优化方案二：函数式风格实现（使用scanLeft） #

用Scala集合的scanLeft方法，一次遍历生成所有起始位置的前缀子序列，代码更简洁：

import scala.collection.mutable.Queue

val q = Queue("golden", "lion", "and", "golden", "lady")

q.indices.foreach { startIdx =>
  // 从startIdx位置开始截取子队列，生成所有前缀字符串
  q.drop(startIdx)
    .scanLeft("") { (acc, elem) =>
      if (acc.isEmpty) elem else s"$acc $elem"
    }
    .tail // 移除初始的空字符串
    .foreach(println)
}

方案说明 #

两种优化方案的核心逻辑一致：

• 遍历每个起始索引startIdx；
• 对于每个起始点，逐步生成从该点开始的所有连续子序列，只遍历元素一次，避免重复计算；
• 前者用StringBuilder优化字符串拼接性能，后者用函数式API更符合Scala风格。

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