Two Sum (opens in a new tab) Easy

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.

You can return the answer in any order.

Example:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Solution:

The brute force approach for this problem is to use two nested loops to check every possible pair of elements in the array. However, this would have a time complexity of O(n^2), which is not optimal for larger input sizes.

A more efficient solution is to use a hash table (also called a map) to store the elements of the array as keys and their indices as values. Then, we can iterate through the array and check if the complement (i.e., the difference between the target and the current element) is in the hash table. If it is, we can return the indices of the current element and its complement.

Here's the code for the optimal solution:

In TypeScript:

function twoSum(nums: number[], target: number) {
	const map = new Map<number, number>();
	for (let i = 0; i < nums.length; i++) {
		const complement = target - nums[i];
		if (map.has(complement)) {
			return [map.get(complement), i];
		}
		map.set(nums[i], i);
	}
	return [];
}

In Python3

def twoSum(self, nums: List[int], target: int) -> List[int]:
	map = {}
	for i in range(len(nums)):
		complement = target - nums[i]
		if complement in map:
			return [map[complement], i]
		map[nums[i]] = i
	return []

The time complexity of this solution is O(n), where n is the length of the input array. The space complexity is also O(n), because we store all the elements of the array in the hash table.