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

问题描述

这是我以前的。
假设我想在给定的排序数组中找到一对整数，它们的和等于给定数字 x 。众所周知的一次通过解决方案如下所示：

This is a follow-up to my previous question.Suppose I want to find a pair of integers, which sum to a given number x, in a given sorted array. The well-known "one pass" solution looks like that:

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中的惰性列表）
您可以推荐一个非递归版本吗？

How would you suggest write functionally without any mutable state ?
I guess I can write a recursive version with Stream (lazy list in Scala)Could you suggest a non-recursive version ?

推荐答案

这是一个相当简单的版本。它创建一个 Stream < Vectors ，它删除每次迭代中的第一个或最后一个元素。然后我们限制无限 Stream （-1，所以你不能在自己中添加一个数字），然后 map 它转换为输出格式并检查目标情况。

Here's a fairly straightforward version. It creates a Stream of Vectors that removes the first or last element on each iteration. Then we limit the size of the otherwise infinite Stream (-1 so you can't add a number with itself), then map it into the output format and check for the target condition.

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 。我强烈建议检查出来。了解它们可以大大简化这样的问题。

There are a lot of gems hidden in the companion objects of Scala's collections, like Stream.iterate. I highly recommend checking them out. Knowing about them can greatly simplify a problem like this.

这篇关于在排序后的数组中找到一对总和为X的整数的函数式方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！