将迭代的两个和k转换为函数

Question

我在Python中有这个代码,它找到数组中总和为k的所有数字对:

def two_sum_k(array, k):
    seen = set()
    out = set()

    for v in array:
        if k - v in seen:
            out.add((min(v, k-v), max(v, k-v)))
        seen.add(v)
    return out

任何人都可以帮助我将其转换为Scala(功能样式)吗？也具有线性复杂性.

Answer 1

我认为这是一个典型的例子,当一个理解能够提供额外的清晰度

scala> def algo(xs: IndexedSeq[Int], target: Int) =
   | for {
   |   i <- 0 until xs.length
   |   j <- (i + 1) until xs.length if xs(i) + xs(j) == target
   | }
   | yield xs(i) -> xs(j)
algo: (xs: IndexedSeq[Int], target: Int)scala.collection.immutable.IndexedSeq[(Int, Int)]

使用它:

scala> algo(1 to 20, 15)
res0: scala.collection.immutable.IndexedSeq[(Int, Int)] = Vector((1,14), (2,13), (3,12), (4,11), (5,10), (6,9), (7,8))

我认为它也不会遇到你的算法存在的问题

Answer 2

我不确定这是最清晰的,但折叠通常可以解决问题:

def two_sum_k(xs: Seq[Int], k: Int) = {
  xs.foldLeft((Set[Int](),Set[(Int,Int)]())){ case ((seen,out),v) =>
    (seen+v, if (seen contains k-v) out+((v min k-v, v max k-v)) else out)
  }._2
}