Scala algorithm: Find triplets that sum to a target ('3Sum')
Find indices of tuples that sum to a target. Assume no duplicates on input.
Test cases in Scala
assert(threeSum(Array.empty, 0).isEmpty) assert( threeSum(Array(-1, 0, 1, 2, -1, -4), 0) == Set(List(-1, 0, 1), List(-1, -1, 2)) )
Algorithm in Scala
39 lines of Scala (compatible versions 2.13 & 3.0).
The normal approach to this problem is to check for all pairings of values, however that is O(n^3) because we would be checking for every triplet possible.
However, what we can do is to build on TwoSum, which is O(n), to get O(n^2), in the same vein as in Twosum. (this is © from www.scala-algorithms.com)
Scala concepts & Hints
'collect' allows you to use Pattern Matching, to filter and map items.
In Scala, the 'Ordering' type is a 'type class' that contains methods to determine an ordering of specific types.
Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.
.viewsyntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.