Solution For Two Sum
The “Two Sum” problem on LeetCode asks us to find two numbers in an array that add up to a given target.
The input for this problem consists of an array of integers and a target integer. We need to find two distinct integers in the array whose sum equals the target.
There are multiple ways to solve this problem, but the most efficient way is to use a hash map. We can iterate through the array, and for each element, check if the difference between the target and the element exists in the hash map. If it does, we have found our solution, and we can return the indices of the two numbers. If it doesn’t, we can add the element and its index to the hash map, and continue iterating through the array.
Here’s the solution in Python:
def twoSum(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
hashmap = {} # initialize an empty hash map to store elements and their indices
for i in range(len(nums)):
if target - nums[i] in hashmap:
# if the difference between target and current element exists in the hash map, we have found our solution
return [hashmap[target - nums[i]], i]
else:
# otherwise, add the current element and its index to the hash map
hashmap[nums[i]] = i
This solution has a time complexity of O(n), where n is the length of the input array, since we iterate through the array once. It also has a space complexity of O(n), since we store elements and their indices in a hash map.
Step by Step Implementation For Two Sum
class Solution { public int[] twoSum(int[] nums, int target) { Mapmap = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] { map.get(complement), i }; } map.put(nums[i], i); } throw new IllegalArgumentException("No two sum solution"); } }
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: # create an empty hash map hash_map = {} # traverse the list and store the values in the hash map for i, num in enumerate(nums): hash_map[num] = i # traverse the list again for i, num in enumerate(nums): # check if the complement exists in the map if target - num in hash_map and hash_map[target - num] != i: return [i, hash_map[target - num]] # if no such pair exists return []
/** * @param {number[]} nums * @param {number} target * @return {number[]} */ var twoSum = function(nums, target) { // create a map to store the complements let map = new Map(); // loop through the array for(let i = 0; i < nums.length; i++) { // check if the complement exists in the map if(map.has(nums[i])) { // return the indices return [map.get(nums[i]), i]; } // store the complement in the map map.set(target - nums[i], i); } };
class Solution { public: vectortwoSum(vector & nums, int target) { //Create an empty vector of pairs to store the result vector result; //Traverse the given vector for(int i = 0; i < nums.size(); i++) { //Search for the element just greater than the current element auto it = lower_bound(nums.begin() + i + 1, nums.end(), target - nums[i]); //If the element is found, then insert both the indices in the result vector if(it != nums.end() && *it == target - nums[i]) { result.push_back(i); result.push_back(it - nums.begin()); break; } } //Return the result vector return result; } };
public class Solution { public int[] TwoSum(int[] nums, int target) { //check for null and empty array if(nums == null || nums.Length == 0){ return null; } //create a map to store the value and index Dictionarymap = new Dictionary (); //loop through the array for(int i = 0; i < nums.Length; i++){ //if map contains the target - current value, return the value if(map.ContainsKey(target - nums[i])){ return new int[] {map[target - nums[i]], i}; } //if map doesn't contain the current value, add it to the map else{ map.Add(nums[i], i); } } //if no match is found, return null return null; } }