Hint to solve in O(n)


#1

There are two possible approaches

  1. You can use either two pointers.
  2. You can use hash tables to store the number of occurrences for every integer.