在排序数组中查找总和为 X 的一对整数的函数式方法

这是我之前的后续question https://stackoverflow.com/questions/42272546/how-to-traverse-array-from-both-left-to-right-and-from-right-to-left。 假设我想找到一对整数，其总和为给定数字x，在给定的排序数组中。众所周知的“一次通过”解决方案如下所示：

def pair(a: Array[Int], target: Int): Option[(Int, Int)] = {

  var l = 0
  var r = a.length - 1
  var result: Option[(Int, Int)] = None
  while (l < r && result.isEmpty) {
    (a(l), a(r)) match {
      case (x, y) if x + y == target => result = Some(x, y)
      case (x, y) if x + y < target => l = l + 1
      case (x, y) if x + y > target => r = r - 1
    }
  }
  result
}

您建议如何在没有任何可变状态的情况下进行功能性编写？
我想我可以写一个递归版本Stream（Scala 中的惰性列表） 您能建议一个非递归版本吗？

这是一个相当简单的版本。它创建了一个Stream of Vectors删除每次迭代中的第一个或最后一个元素。然后我们限制原本无限的大小Stream（-1，所以你不能将数字与自身相加），然后map将其转换为输出格式并检查目标条件。

def findSum(a: Vector[Int], target: Int): Option[(Int, Int)] = {
  def stream = Stream.iterate(a){
    xs => if (xs.head + xs.last > target) xs.init else xs.tail
  }

  stream.take (a.size - 1)
        .map {xs => (xs.head, xs.last)}
        .find {case (x,y) => x + y == target}
}

Scala 集合的伴生对象中隐藏着很多宝石，例如Stream.iterate。我强烈建议您检查一下。了解它们可以大大简化这样的问题。