Two Sum

Given an array of integers and a target, return the indices of the two numbers that add up to the target. Exactly one answer exists, and you can't use the same element twice.

A way to picture it

It's a dance party. Every number walks in looking for the one partner that makes the target. Instead of asking everyone in the room, it checks the guest list at the door: has my partner already arrived?

How to approach it

For each number x, the partner you need is target βˆ’ x. A hash map of the numbers you've already seen answers β€œis my partner here?” in O(1).

Example

Input: {"nums":[2,7,11,15],"target":9}. Output: [0,1].

Complexity: O(n) time and O(n) space. One pass over the array; the map may end up holding every number.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.