class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for lp in range(len(nums)):
for rp in range(lp + 1, len(nums)):
if (nums[lp] + nums[rp]) == target:
return [lp,rp]
Optimal Solution:
Time complexity - O(n)
Space complexity - O(n)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i in range(len(nums)):
diff = target - nums[i] # diff could be a key (value from arr)
if diff in seen.keys():
# Check for diff in key array in dict here
return [i, seen[diff]]
seen[nums[i]] = i
print(seen.values())
How this solution works is that we loop through the array and look for what the difference between a target and the value at an index is. Based on this difference we look to see if it is already there in the hashmap we created and if it is, we simply return the index of that value alongside the other value we first found the difference in.
Very simply put, per value in the array we look for the difference between the target value and the value at the current index we are in. Once we find the diff, we look for a value that is equal to that diff in the seen hashmap, if not we simply append the current value and index we have into the seen dict. Afterwards, we move ahead and repeat this until we find a diff that exists in our keys and return the index from the associated value.
So, returned value is going to be [i, seen[diff] given that the keys are the actual values and the values in the dict are the indexes.