Scala algorithm: Find indices of tuples that sum to a target (Two Sum)
Find indices of tuples that sum to a target. Assume no duplicates on input.
Test cases in Scala
assert(twoSum(Array.empty, 0).isEmpty, "Empty array has no result") assert( indexArray(Array(-1, 2)) == Map(-1 -> 0, 2 -> 1), "We can map numbers to their indices" ) assert(twoSum(Array(-1, 0, 1, 3, -3, -4), 0) == Set(Set(0, 2), Set(3, 4)))
Algorithm in Scala
10 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!
The normal approach to this problem is to check for all pairings of values, however that is O(n^2).
In the faster version, we can put the values into a map, and then look up 'target - num' to find if there is a match for the other number for the target number (because 'num1 + num2 = target', then 'num2 = target - num1'. (this is © from www.scala-algorithms.com)
This takes to O(n) which is a good fast solution. We also use Sets to represent the indices since they may be out of order.
Scala concepts & Hints
The for-comprehension is highly important syntatic enhancement in functional programming languages.
.viewsyntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.