keithdsouza

//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