Учитывая массив целых чисел, верните индексы двух чисел таким образом, чтобы они складывались до указанной c цели с Scala

Question

Я практикую Scala, решая все go вопросы и застрял на этой проблеме из leetcode:

Учитывая массив целых чисел, возвращайте индексы двух чисел так, чтобы они в сумме составляли конкретная цель c. Вы можете предположить, что для каждого ввода будет ровно одно решение, и вы не можете использовать один и тот же элемент дважды.

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, так как для каждого ввода я получаю в результате массив (-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? При обновлении элементов с помощью изменяемой карты я ссылался на этот пост .

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))
}

Answer 2

Вы можете эмулировать то, что вы бы делали на императивном языке, вложенном для.
(примечание: я немного изменил подпись, чтобы она была более идиоматической c, вы можете просто вызвать эту функцию на оригинальный, адаптирующий входы и выходы)

import scala.collection.immutable.ArraySeq // Immutable array, only exists on 2.13

def twoSum(nums: ArraySeq[Int], target: Int): Option[(Int, Int)] =
  Iterator
    .range(start = 0, end = nums.length)
    .map { i =>
      Iterator
        .range(start = (i + 1), end = nums.length)
        .collectFirst {
          case j if ((nums(i) + nums(j)) == target) =>
            (i, j)
        }
    } collectFirst {
      case Some(tuple) => tuple
    }

Что вы можете использовать, например:

twoSum(ArraySeq(1, 3, 5, 2, 0, 4), target = 8)
// res: Option[(Int, Int)] = Some((1,2))

twoSum(ArraySeq(1, 3, 5, 2, 0, 4), target = 10)
// res: Option[(Int, Int)] = None