scala - 给定一个整数数组，使用 Scala 返回两个数字的索引，使它们相加达到特定目标

Question

我通过解决算法问题来练习 Scala，并在 leetcode 中解决了这个问题:

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

我想出了以下代码

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    val map = scala.collection.mutable.Map.empty[Int, Int]
    nums.zipWithIndex.foreach{ case(num, idx) => 
        map.get(idx) match {
            case Some(r) => return Array(r, idx)
            case None => map += (idx -> (target-num))
       }
    }
    Array(-1, -1)
}

看来我以错误的方式向 map 添加值，因为对于每个输入，我都会得到一个 Array(-1,-1) 作为结果。

预期的灵魂。

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    var map = Map.empty[Int, Int]
    for ((v, i) <- nums.zipWithIndex) {
       map.get(v) match {
           case Some(r) => return Array(r, i)
           case None => map ++= Map((target - v) -> i)
       }
    }
    Array(-1, -1)
}

你能指出我的错误并解释如何正确更新 hashMap 吗？在使用可变 Map 更新元素时​​，我引用了此 post 。

Answer 1

在第二个解决方案中，您有一个值到索引的映射，这是正确的。但在第一个中，您有相反的情况:从索引到值的映射，这是错误的。因此，您必须反转添加到 Map 中的条目:

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
  val map = scala.collection.mutable.Map.empty[Int, Int]
  nums.zipWithIndex.foreach{ case(num, idx) =>
    map.get(num) match {                     // Changed: retrieving the index of the value 
      case Some(r) => return Array(r, idx)
      case None => map += ((target-num) -> idx)  // Changed: adding (value -> index) pairs
    }
  }
  Array(-1, -1)
}

---

郑重声明，如果您想避免使用可变性和 return，最简单的方法是一次预先计算 Map，然后执行第二遍查找两个索引:

import scala.collection.immutable.HashMap

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
  val indexByValue = HashMap(nums.zipWithIndex: _*)
  val result = nums.indices.collectFirst(Function.unlift { i =>
    indexByValue.get(target - nums(i)).filter(_ != i).map(Array(i, _))
  })
  result.getOrElse(Array(-1, -1))
}

这仍然比可变版本慢，因为它对 nums 进行了两次传递，并急切地构建整个 Map，而原始的可变代码只进行了一次传递并延迟构建Map。要以函数方式在一次传递中延迟计算 Map，您可以在迭代器或某些延迟集合上使用 scanLeft:

import scala.collection.immutable.HashMap

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
  nums.indices.iterator
    .scanLeft(HashMap.empty[Int, Int]) { (map, i) =>
      map + (nums(i) -> i)
    }
    .zipWithIndex
    .collectFirst(Function.unlift { case (indexByValue, i) =>
      indexByValue.get(target - nums(i)).filter(_ != i).map(Array(i, _))
    })
    .getOrElse(Array(-1, -1))
}