Scala实现两数之和的两种解法Big-O复杂度分析求证

我正在分析LeetCode经典两数之和问题的两种Scala解法的时间与空间复杂度。原本以为尾递归解法更优，但初步判断两种解法的时间复杂度均为O(n)、空间复杂度均为O(n)，想请大家验证该判断是否正确。

输入示例 #

inputArray = Array(4, 6, 5)
sumToCheck = 9

Scala代码实现 #

import scala.annotation.tailrec
import scala.collection.mutable.ListBuffer

def checkTwoSum(inputArray: Array[Int], sumToCheck: Int): Boolean = {
  val subtractList: ListBuffer[Int] = ListBuffer.empty
  var output = false
  for (i <- inputArray.indices) {
    if (subtractList.contains(inputArray(i))) {
      output = true
    }
    else {
      subtractList += sumToCheck - inputArray(i)
      }
  }
  output
}

def checkTwoSumRec(inputArray: Array[Int], sumToCheck: Int): Boolean = {

  @tailrec
  def inner(input: Array[Int], subtractList: Array[Int] = Array.emptyIntArray): Boolean = {
    if (input.isEmpty) {
      false
    }
    else if (subtractList.contains(Option(input.head).getOrElse(0))) {
      true
    }
    else {
      inner(input.tail, subtractList :+ (sumToCheck - Option(input.head).getOrElse(0)))
    }

  }

  inner(inputArray)

}

复杂度分析与验证 #

你的初步判断并不准确，两种解法的时间复杂度都不是O(n)，空间复杂度也存在差异：

1. 迭代版（checkTwoSum） #

• 时间复杂度：O(n²)。循环执行n次，每次调用subtractList.contains时，ListBuffer的contains是线性遍历操作，平均每次遍历长度为n/2的集合，总时间开销为O(n²)。
• 空间复杂度：O(n)。最坏情况下，ListBuffer会存储n个元素（当数组中没有符合条件的两数组合时），空间开销与输入规模线性相关。

2. 尾递归版（checkTwoSumRec） #

• 时间复杂度：O(n²)。递归执行n次，每次调用subtractList.contains时，Scala数组的contains同样是线性遍历操作，总时间开销为O(n²)。
• 空间复杂度：O(n²)。虽然尾递归优化会让栈空间保持O(1)，但每次递归调用时subtractList :+ ...会创建一个新数组（Scala数组是不可变的），最坏情况下会生成长度从0到n-1的n个数组，总空间开销为O(n²)。

优化建议 #

如果要达到O(n)时间复杂度，应该改用哈希表（比如Scala的mutable.HashMap）存储需要查找的元素，因为哈希表的contains操作是O(1)平均时间复杂度，这样两种解法都能将时间复杂度降到O(n)，空间复杂度保持O(n)。

内容的提问来源于stack exchange，提问作者Дмитрий Ходырев