Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package org.geo.scala.fundamentals.examples.numerical
- import scala.collection.mutable._
- /**
- * @author george
- * This class will find the number of unique pairs that equal
- * to some input sum in an input array
- *
- * @param a Int array containing numbers to look for pairs in
- * @param n Int sum we are trying to find in a
- *
- */
- class PairsSummingToN(val a: Array[Int], val n: Int) {
- require(n > 0)
- require(a.length > 1)
- /**
- * @return list of pairs that may contain duplicates
- */
- def getPairsEqualingToSumList(): ListBuffer[(Int, Int)] = {
- val listOfPairs = new ListBuffer[(Int, Int)]()
- val map: Map[Int, ListBuffer[Int]] = new HashMap[Int, ListBuffer[Int]]()
- a.indices.foreach(i => {
- val x = -(a(i) - n)
- val m = map get x
- if (m == None) {
- /** put a new map entry into the value of map **/
- map += (x -> ListBuffer(i))
- } else {
- /** get the map out and update it **/
- val mi = m.get
- mi += (i)
- }
- val f = map get a(i)
- if (f != None) {
- val lb = f.get
- listOfPairs += ((a(i), a(f.get.apply(f.get.size - 1))))
- }
- })
- listOfPairs
- }
- /**
- * @return A unique set of pairs without duplicates
- */
- def getPairsEqualingToSumSet(): Set[(Int, Int)] = {
- val setOfPairs = new HashSet[(Int, Int)]()
- val map: Map[Int, ListBuffer[Int]] = new HashMap[Int, ListBuffer[Int]]()
- a.indices.foreach(i => {
- val x = -(a(i) - n)
- val m = map get x
- if (m == None) {
- /** put a new List into the value of map **/
- map += (x -> ListBuffer(i))
- } else {
- /** get the list out and update it **/
- val mi = m.get
- mi += (i)
- }
- val f = map get a(i)
- if (f != None) {
- val lb = f.get
- setOfPairs += ((a(i), a(f.get.apply(f.get.size - 1))))
- }
- })
- setOfPairs
- }
- }
- object PairsSummingToN {
- def getPairs(tyP: Boolean)(a: Array[Int], n: Int) = {
- val solutionSet = new PairsSummingToN(a, n)
- tyP match {
- case true => solutionSet.getPairsEqualingToSumList()
- case false => solutionSet.getPairsEqualingToSumSet()
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement