Find indices of tuples that sum to a target. Assume no duplicates on input.
Test cases in Scala
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.