2 sum算法的改进解

Question

我尝试在 leetcode ( https://leetcode.com/problems/two-sum/#/description )中找出算法的功能实现

我想我需要的是 3 个函数，如下所示：

• List[Int] => List[(Int, Int)] 用位置压缩元素
• List[(Int, Int)], Int, Int => List[((Int, Int) , (Int, Int))] 用剩余的元素和位置压缩元素和位置，并使用 Sum 进行过滤
• List[((Int, Int) , (Int, Int))] => List[(Int, Int)] 映射到位置

代码如下所示：

  def findTwoSumElements(xs: List[Int], sum: Int): List[(Int, Int)] = {
    val zipWithIndex = xs.zipWithIndex
    var tailElements = zipWithIndex

    val result = zipWithIndex.map(t => {
      val element = zipAndFilter(tailElements, t, sum)
      tailElements = tailElements.tail
      element
     }
    )

    result.flatten.map(t => (t._1._2, t._2._2))
  }

  private def zipAndFilter(xs: List[(Int, Int)], x: (Int, Int), sum: Int): List[((Int, Int), (Int, Int))] = {
    xs.map(t => (t, x)).filter(t => (t._1._1 + t._2._1) == sum)
  }

 println(findTwoSumElements(List(1,2,3,4), 10)) //List()
 println(findTwoSumElements(List(1,2,3,4), 7)) //List((3,2))
 println(findTwoSumElements(List(1,2,3,4), 5)) //List((3,0), (2,1))
 println(findTwoSumElements(List(), 5)) //List()

我想通过不使用来改进这部分代码 var

  var tailElements = zipWithIndex

  val result = zipWithIndex.map(t => {
     val element = zipAndFilter(tailElements, t, sum)
     tailElements = tailElements.tail
     element
   }
  )

原因是我想去掉重复的Tuple[Int, Int]，比如如果我不改变尾部，它会一起返回(x, y)和(y, x)

我可以有一些关于如何改进它以及整个实现的建议或演示代码吗

Answer 1

对于每个输入都只有一个解决方案的简化问题，您可以将解决方案编写为单行：

def twoSum(nums: List[Int], target: Int): List[Int] =
  nums.combinations(2).find(_.sum == target).get.map(nums.indexOf)

扩展的解决方案，具有显式类型：

def twoSum(nums: List[Int], target: Int): List[Int] = {
  val comb: Iterator[List[Int]] = nums.combinations(2) // Get 2-sized combinations iterator
  val find: Option[List[Int]] = comb.find(_.sum == target) // Find the first (and only) combination having sum equals to our target
  val res: List[Int] = find.get // Exactly one solution
  val idx: List[Int] = res.map(nums.indexOf) // Get the indexes in the original list
}

一种替代的通用解决方案，它允许多个结果或根本没有结果（返回List[List[Int]]）：

 def twoSum(nums: List[Int], target: Int): List[List[Int]] =
   nums.combinations(2).collect {
     case couple if couple.sum == target =>
       couple.map(nums.indexOf)
   }.toList

它可以更广泛地接受组合大小（2在我们的示例中）作为参数