FindTargetSumInArray.java

//assumes array is sorted and runtime is O(n) otherwise O(n log n)
  public static boolean findTargetSumInArray(int[] subject, int target) {
    if(subject == null || subject.length < 2) return false; //can't have less than 2 elements for this

    int length = subject.length - 1; //the lenght of array we deal with

    if(subject[0] + subject[length] == target) return true; //lucky guess
    if(subject[length-1] + subject[length] == target) return true; //another guess which optimizes condition below
    // we can't have any target greater than the sum of the last two elements which are the two largest
    //proven by 1,2,3,5 or 100, 700, 900, 999
    if(target > subject[length-1] + subject[length]) return false;

    //create a map of elements with how many times they appear in the array, runs in O(n) time and constant time
    //takes worst case O(n) space
    Map<Integer, Integer> elementsAndCounts = new HashMap<>();
    for(int i = 0; i <= length; i++) {
      int count = 1;
      int currentSubject = subject[i];
      if(elementsAndCounts.containsKey(currentSubject)) {
        count += elementsAndCounts.get(currentSubject);
      }
      elementsAndCounts.put(currentSubject, count);
    }

    //optimal when there are duplicates in the array
    //worst case size O(n) best case O(n - m) where m is number of duplicates
    //can be avoided if we can confirm there are no duplicates, but very valuable if there are
    Set<Integer> visited = new HashSet<>();


    //Worst case O(n) operations to find if two items sum up to target
    //best case O(n-m) if there are m duplicates in the array
    for(int i = 0; i < subject.length; i++) {
      int currentSubject = subject[i]; // current element
      int newTarget = target - currentSubject; //what we want to search for now
      //we want to have at-least two elements if we are looking for a target same as the current one or 1 otherwise
      int minimumCount = newTarget == currentSubject ? 2 : 1;
      Integer count; //constant variable for checks below

      /**
       * return true when
       * 1. we did not see the element earlier proven by Set.add(currentSubject) which will return false if we saw it earlier
       * 2. if the newTarget we are looking for exists in our Map from earlier computation
       * 3. And count of that element being greater or equal to minimumCount we set based on equality of newTarget to currentElement
       */
      if(visited.add(currentSubject)
          && (count = elementsAndCounts.get(newTarget)) != null
          && count >= minimumCount) {
        return true;
      }
    }
    return false;
  }