Find all pairs in an array that sum to a given number

Assume you have an array of random integers and a sum value. Find all
pairs of numbers from the array that sum up to the given sum in O(n)
time. Find all distinct pairs. (1,2) and (2,1) are not distinct.

import java.util.HashSet;

public class PairsSummingToElement {

  public static void main(String[] args) {
    PairsSummingToElement e = new PairsSummingToElement();
    int[] input = new int[] { 2, 5, 3, 7, 9, 8 };
    int sum = 11;
    HashSet result = e.findAllPairs(input, sum);
    for (Pair p : result) {
      System.out.println("(" + p.getElement1() + "," + p.getElement2() + ")");
    }

  }

  public HashSet findAllPairs(int[] inputList, int sum) {
    HashSet allElements = new HashSet();
    HashSet substracted = new HashSet();
    HashSet result = new HashSet();

    for (int i : inputList) {
      allElements.add(i);
      substracted.add(i - sum);
    }

    for (int i : substracted) {
      if (allElements.contains(-1 * i)) {
        addToSet(result, new Pair(-i, i + sum));
      }
    }

    return result;

  }

  public void addToSet(HashSet original, Pair toAdd) {
    if (!original.contains(toAdd) && !original.contains(reversePair(toAdd))) {
      original.add(toAdd);
    }
  }

  public Pair reversePair(Pair original) {
    return new Pair(original.getElement2(), original.getElement1());
  }

}

class Pair {
  private int element1;

  private int element2;

  public Pair(int e1, int e2) {
    element1 = e1;
    element2 = e2;
  }

  public int getElement1() {
    return element1;
  }

  public int getElement2() {
    return element2;
  }

  public int hashCode() {
    return (element1 + element2) * element2 + element1;
  }

  public boolean equals(Object other) {
    if (other instanceof Pair) {
      Pair otherPair = (Pair) other;
      return ((this.element1 == otherPair.element1) && (this.element2 == otherPair.element2));
    }
    return false;
  }

}

No comments on the time complexity, I do have a bunch of other comments:

Code to interfaces, not implementations

It's better to use Set allElements = new HashSet() (side note: guess you're not on >= Java 7, since you can use diamond operators otherwise) so that users of allElements do not need to know that it actually is a HashSet. This is just good practice. The lesson here is that it allows the programmer to replace the implementation with another in the future when required.

Does not contain, then add to a Set

In the following code block:

if (!original.contains(toAdd) && !original.contains(reversePair(toAdd))) {
  original.add(toAdd);
}

I think the extra check !contains() is not really required because Set.add()'s Javadoc says:


If this set already contains the element, the call leaves the set unchanged and returns false.

So, even if original did contain toAdd, calling add() will leave the set unchanged anyways. I guess this is useful when you're running on a large set of inputs so that there is some short-circuiting done, hence this is strictly just 'food-for-thought' and not something to frown upon.

hashCode()

I'm guess there's an implied range of inputs such as all must be positive right? Because your calculation (element1 + element2) * element2 + element1 will yield the same hash codes when element1 + element2 equals to 1, and having a bunch of negative and positive integers (or just 0, 1) will 'break' this easily. You may want to update your question with any assumptions on the range of inputs.

How to reverse a Pair

I think that you can move your method reversePair(Pair) into the Pair class itself as such:

public final class Pair { // also declared as final

    private final int element1; // also declared as final
    private final int element2; // also declared as final

    public Pair(int element1, int element2) {
        this.element1 = element1;
        this.element2 = element2;
    }
    ...

    public Pair getReverse() {
        return new Pair(element2, element1);
    }
}

Using it then becomes slightly easier:

if (!original.contains(toAdd.getReverse())) {
  original.add(toAdd);
}

Override toString()

Oh yeah, given how you want to print the contents of Pair objects in the end, why not just override toString() too? :)

StackExchange Code Review Q#83950, answer score: 5