Перевести итерационные две суммы 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
}

Answer 3

Вы можете просто отфильтровать (k-x <= x), используя только те x в качестве первого элемента, которые не больше k / 2: </p>

def two_sum_k (xs: List[Int], k: Int): List [(Int, Int)] =
  xs.filter (x => (x <= k/2)).
    filter (x => (xs contains k-x) && (xs.indexOf (x) != xs.lastIndexOf (x))).
      map (x => (x, k-x)).distinct

Мой первый фильтр в строке 3 был просто filter (x => xs contains k-x)., что не удалось, как было найдено в комментарии Someone Else. Теперь все сложнее и не находит (4, 4).

scala> li
res6: List[Int] = List(2, 3, 3, 4, 5, 5)

scala> two_sum_k (li, 8) 
res7: List[(Int, Int)] = List((3,5))

Answer 4

Ну, прямой перевод был бы таким:

import scala.collection.mutable

def twoSumK[T : Numeric](array: Array[T], k: T) = {
  val num = implicitly[Numeric[T]]
  import num._

  val seen = mutable.HashSet[T]()
  val out: mutable.Set[(T, T)]  = mutable.HashSet[(T, T)]()

  for (v <- array) {
    if (seen contains k - v) out += min(v, k - v) -> max(v, k - v)
    seen += v
  }

  out
}

Один умный способ сделать это был бы:

def twoSumK[T : Numeric](array: Array[T], k: T) = {
  val num = implicitly[Numeric[T]]
  import num._

  // One can write all the rest as a one-liner
  val s1 = array.toSet
  val s2 = s1 map (k -)
  val s3 = s1 intersect s2

  s3 map (v => min(v, k - v) -> max(v, k - v))
}

Answer 5

def twoSumK(xs: List[Int], k: Int): List[(Int, Int)] = {
  val tuples = xs.iterator map { x => (x, k-x) }
  val potentialValues = tuples map { case (a, b) => (a min b) -> (a max b) }
  val values = potentialValues filter { xs contains _._2 }
  values.toSet.toList
}

Answer 6

Это делает трюк:

def two_sum_k(xs: List[Int], k: Int): List[(Int, Int)] ={
      xs.map(a=>xs.map(b=>(b,a+b)).filter(_._2 == k).map(b=>(b._1,a))).flatten.collect{case (a,b)=>if(a>b){(b,a)}else{(a,b)}}.distinct
}