Description: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Brute-force Approach

Iterate through the array, and for each element, iterate through the rest of the array in a nested loop to find if any pair sums to the target.

Time: O(n^2)

Space: O(1)

Better Approach

Sort the array and use two pointer approach, one at the start and one at the end. If the sum is less than the target, increment the left pointer. If the sum is greater than the target, decrement the right pointer.

Time: O(nlogn)

Space: O(1)

Optimal Approach

Iterate through the array, inserting each element into a hashmap. Simultaneously, for each element, check if (target - element) exists in the hashmap.

Time: O(n)

Space: O(n)