Two Sum

Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.

You may assume that every input has exactly one pair of indices i and j that satisfy the condition.

Return the answer with the smaller index first.

Example 1:

Input:
nums = [3,4,5,6], target = 7

Output: [0,1]

Explanation: nums[0] + nums[1] == 7, so we return [0, 1].

def twoSum(nums: List[int], target: int) -> List[int]:
	m = {} # val -> idx
	for i in range(len(nums)):
		diff = target - nums[i]
		if diff in m:
			return [m[diff], i]
		m[nums[i]] = i

Solution	Time	Space
Brute Force	$O (n^{2})$	$O (1)$
Sorting	$O (n \log n)$	$O (n)$
Hash map (2 and 1 pass)	$O (n)$	$O (n)$