Given an array of integers input[] and an integer target, the task is to return the index of two numbers such that they sum up to target.
Input: nums = [1, 4, 45, 6, 10, 8], target = 16
Output: [3,4]
Input: nums = [3,2,4], target = 6
Output: [1,2]
Input: nums = [3,4], target = 6
Output: [-1,-1]
Solutions
Method 1: In O(n) time and O(n) space
We can solve this problem in O(n) time and O(n) space.
The goal is to keep a hash map with the key representing target-a[i] and the value representing the index.
Iterate through the array from left to right; if target-currentElement is already in the map, return [map.get(target-currentElement), i]; otherwise, add the current element value and index to the map.
Complexity
The time complexity of this solution is O(n) and space complexity is O(n).
Method 2: In O (n log n) time and O(1) space
We can solve this problem in O(n log n) time and O(1) space.
The idea is to first sort the array and then use two pointers at both ends of the array. i.e. i=0, j= a.length-1.
If i+j < target, do i++, else if i+j > target, do j--, else return return [i, j].
Complexity
The time complexity of this solution is O(n log n) and space complexity is O(1).
Method 3: In O(n*n) time and O(1) space
We can solve this problem in O(n2) time using two nested loops.
The idea is to check for every pair until the target is met; if no pair sums up to the target, return [-1, -1].
Complexity
The time complexity of this solution is O(n*n) and space complexity is O(1).