In this question, we are given an array of integer nums and an integer target, and we are asked to return two distinct indices such that the numbers in those positions add up to be the target. The question assumes that there is one and only one solution for each input.
Approach 1: Brute Force
Traverse the array. For each number num in the array, traverse the rest of the array to see if target - num can be found.
For example:
Java implementation:
For time complexity, let n be the length of the integer array. In the outer loop, we traverse each element once, hence it’s O(n); in the inner loop, we traverse the rest of array once, in the worst case it’s also O(n). The overall time complexity would be O(n*n) = O(n²).
For space complexity, we don’t use any additional space in the solution, hence it’s O(1).
Approach 2: Sorting
Sort the input array in ascending order, then use two pointers(starting from the left-most and right-most position) to find the two numbers that sum up to target.
For sorting the array, we can apply various approaches, e.g. merge sort, quick sort, bubble sort, etc.
It is worth noting that we have to return the original indices of the two numbers in the array. By sorting the array we lose the position information, hence we have to save this information somewhere else. One way is to store each number and corresponding index in a 2D array. You can also create a class for this structure as well.
Here is an example:
Java implementation:
For time complexity, it’s O(n*log(n)) where n is the length of the array nums, if we apply sorting algorithms like merge sort.
For space complexity, it’s O(n) since we created a 2D array of size n to hold both the number values and their corresponding indices.
Approach 3: Hash Table
In the brute force approach, we have to loop through the rest of the array again and again to find if a possible solution exists, which is very time consuming. One possible improvement is to make this process faster.
Then the question now becomes: given an array of numbers, how to check if a number exists in the array and if so, what is the number’s index.
Now you see hash table fits this new question perfectly. We can either build the hash table from the beginning or the other way around. Personally I’ll pick the way to build from the beginning as it’s easier for me to understand: you start with an empty hash table, and loop through each element in the array, if you find a key in the hash table that has a sum of target with this element, you are done; otherwise you put this element and its index value into the hash table since you’ve “seen” it.
Here is an example:
Java implementation:
For time complexity, it’s O(n) where n is the length of the array.
For space complexity, it’s O(n) since in the worst case we have to store all the elements and their corresponding indices in the map.
