This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code Two Sum problem. This is a Leet code problem named two Sum. We will solve it using python and it is the best space and time optimized solution.
Question of Two Sum Problem
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
If you’re given an array of integers and a goal sum, find the indices of two numbers in the array that add up to the target sum. It’s reasonable to suppose that each input has precisely one answer. You can’t use the same element again, either. You may return the answers in any order you like.
Example
Example 1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
We will use the hashmap approach to solve the Two Sum problem. The aim is to store the indices of the elements that have previously been viewed in a hashmap. The number in the supplied input array is the hashmap’s “key” (You add this to the hashmap as you visit each element). The index of the integer in the array represented by the hashmap key is the “value” of the hashmap. At every step, we will check that key is present in seen variable or not. If it is present then we simple get the index of that key.
Variables and its usage
We will only use one extra variable i.e. seen to store the elements which we have visited. We will use the dictionary data type here which uses key-value pair for storage. We store the visited number in the key and the index of that number as a value.
Example:
Suppose we have an array – [1,3,5,7,9]
So when we visit the first element we will save it in a seen variable like: seen{1:0}
where 1 is the key and 0 is the value
Algorithm
This method performs the following steps for a given input array:
Create a hashmap using integer datatypes as both the key and the value.
Starting with the first element, iterate through each element in the supplied array.
Check if the needed number (required number = targeted sum – current number) is present in the hashmap at each iteration.
If present, return the result as necessary number index, current number index.
Otherwise, make a hashmap with the current iteration number as the key and its index as the value.
Rep till you get the desired outcome or reach the end of the array.
Python Code for Two Sum
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
#nums is list of given numbers
# target is the given sum which is to be find
#seen is a dictonary we have created to store data
seen = {}
#for loop to iterate to each array
for i, value in enumerate(nums):
remaining = target - nums[i]
#we find ramaining and check it is in seen or not
if remaining in seen:
#if find then return current index and index of remaining
return [i, seen[remaining]]
#otherwise add it in seen
seen[value] = i
