U9gc1Bpa

1203 - Two Sum
2
3Given an array of integers and a target, return a pair of indices where the corresponding values in the array add up to the target.
4
5Input: Array of Integers, Target Integer
6Output: Two element Array of Integers
7Example
8Input: [1, 6, -5, 7, 3], -2      =>	Output: [2,4]
9Input: [1, 9, 10], 8			=>	Output: [-1,-1]
10
11Constraints
12
13Time Complexity: O(N)
14Auxiliary Space Complexity: O(N)
15
16If the target integer is not found return [-1, -1].
17
18Values of the array can be positive or negative integers.
19Solution
20
21    Create a hash table
22    Loop through array
23    For each element in array check if that key exists in the hash
24        If it does not exist, take the difference between n and the integer and add that as a key and the index as the value into the array and continue the loop
25        Otherwise if the key exists, return an array with the value found from the hash and the current index
26    If it completes the loop without finding a match, return [-1, -1]
27
28Notes
29
30The naive solution is O(N^2) time which takes every possible pair and compares the sum to the target value, however only uses O(1) space.
31
32This solution takes only O(N) time but increases the space to O(N) as well.