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) {
        Map map = 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:
    vector twoSum(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
        Dictionary map = 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;
    }
}