Two Pointers

Notice that the question prompt explicitly said that the input array may not be sorted. But what if it was guaranteed to be sorted? How can we use that property to help us?

If you've checked out the two pointers tutorial, you might have a guess at how we'll approach this.

See, if the input array is sorted as such:

[1, 2, 3, 4, 6, 7]

And, say we had to find two numbers summing up to 6-- instead of testing every pair, we can start with a pair, and then get information about how close or far we are from our goal. Using that information, we know whether we need smaller numbers (sorted array, so we can go left) or larger numbers (sorted array, so we can go right).

xxxxxxxxxx

const nums = [1, 2, 3, 4, 6, 7];

const goal = 6;

​

function twoSum(nums, goal) {

  let start = 0;

  let end = nums.length - 1;

​

  while (start <= end) {

    const curr = nums[start] + nums[end];

​

    if (curr > goal) {

      end -= 1;

    } else if (curr < goal) {

      start += 1;

    } else {

      return [start, end];

    }

  }

​

  return [];

}

​

console.log(twoSum(nums, goal));