Given an array of integers
nums and an integer
target, return indices of the two numbers such that they add up to
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Input: nums = [2,7,11,15], target = 9
Explanation: Because nums + nums == 9, we return [0, 1].
Input: nums = [3,2,4], target = 6
Input: nums = [3,3], target = 6
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
- Only one valid answer exists.
I have written 3 solutions for the same problem with three different time complexities.
O(n²) or Quadratic time
This is a simple solution that uses the Brute Force method to check every possible pair in an array to find the target solution.
The outer loop compares each element to the rest of the n-1 elements, for each element in the array thus time complexity is O(n²).
O(n * n/2)
The below code also uses the brute force method, but the inner loop runs only half the size of the array instead of going through the whole array each time.
Thus the time complexity of the outer loop is O(n) because it goes through the whole array, and the time complexity of the inner loop is O(n/2), combining both we get O(n * n/2) as the time complexity for the below code.
O(n) or linear time
The time complexity of the below code is O(n), it goes through the whole array only once, this was possible because of the constant time complexity of hashmap for getting an item out of it.