import javafx.util.Pair; //available in Java 1.8

public class Solution {

  public static boolean twoSum(int[] a, int target) {
    Map<Integer, Pair> map = new HashMap<>();
    for(int i=0; i<a.length; i++) { //O(n) where n=a.length
      if (!map.containsKey(a[i])) { //don't insert duplicates
        map.put(a[i], new Pair<Integer, Integer>(target-a[i], i));
        //key is every unique element, value is a pair of numberToFind and position of element first found
      }
    }
    for(int i=0; i<a.length; i++) { //O(n) where n=a.length
      if (map.containsKey(target-a[i])) { //check if there exists numberToFind which adds up with current element to target
        if (i != (int) map.get(target-a[i]).getValue()) {
          //and if that numberToFind is at a different position in the array (handles duplicates)
          return true;
        }
      }
    }
    return false;
  }

  public static void main(String[] args) {
    int[] a1 = {5, 4, 2, 4};
    int[] a2 = {5, 1, 2, 4};
    int[] a3 = {5, 4, 2, 3};
    int target = 8;
    System.out.println(twoSum(a1, target));
    System.out.println(twoSum(a2, target));
    System.out.println(twoSum(a3, target));
  }

}