如何使用 Scala 遍历数字列表并检查是否有成对的数字加起来等于给定值？

Question

我必须生成一个小于给定数字的素数列表，然后找到所有生成的素数对加起来等于该值。

例如数 = 12

smaller_primes = 列表(3, 5, 7, 11)

理想的结果：List((5, 7))

我生成较小素数列表没有问题，但我不知道如何检查哪些对满足要求。这是我试过的：

def check_sum(n: Int) = 
    val get_primes = (List.range(2, n)).filter(num => check_prime_bool(num))  // generating list of smaller prime numbers
    val x = for {
        a <- get_primes
        b <- get_primes
        if a + b == n 
    } yield (a,b)
    x

这个解决方案有效，但我不能使用 for/yield 构造，我只能使用 map()、filter() 等函数

Answer 1

与您已经实施的相同的实施，但使用地图，...将是：

def checkSum(n: Int) = {
  val getPrimes = ((2 to n).filter(check_prime_bool)
  getPrimes.flatMap { a => 
    getPrimes.map(b => (a, b)).filter(b => a + b == n)
  }
}

这样理解，for comprehension 中的第一个反向箭头被编译为：getPrimes.flatMap { a => }（您在 for comprehension 中将迭代变量命名为“a”）。 for comprehension的第二行编译成：getPrimes.map { b => }（注意变量“b”的名字，跟你传递的一样）。 "if" 被编译成 .withFilter 方法，你可以用 filter 代替。

但是如果你愿意，我可以建议另一种实现方式，它是 tailrec 并且是 O(n) 而不是 O(n^2) （它不使用 map，flatMap，...，如果有人可以的话为这种方法提出更好的实施建议，欢迎您编辑此答案）：

import scala.annotation.tailrec

// assuming primes are sorted (since (2 to n).filter(isPrime) which you're using in this case, is sorted)
@tailrec
def checkSum(primes: Array[Int], acc: List[(Int, Int)] = List.empty, leftIndex: Int = 0, rightIndex: Int, num: Int): List[(Int, Int)] = {
  if (leftIndex >= rightIndex) acc // pointers have reached each other, that's the end of the list
  else {
    val left = primes(leftIndex)
    val right = primes(rightIndex)
    val sum = left + right
    if (sum == num) checkSum(primes, (left -> right) +: acc, leftIndex + 1, rightIndex - 1, num)
    else if (sum < num) { // move left pointer to right
      checkSum(primes, acc, leftIndex + 1, rightIndex, num)
    } else { // move right pointer to left
      checkSum(primes, acc, leftIndex, rightIndex - 1, num)
    }
  }
}

val primeNumbers = (2 to 12).filter(isPrime).toArray
checkSum(primeNumbers, rightIndex = primeNumbers.length - 1, num = 12) 
// => List[(5, 7)]

如何使用 Scala 遍历数字列表并检查是否有成对的数字加起来等于给定值？

How to iterate over a List of numbers and check if there are pairs of numbers that add up to a given value using Scala?

scala