Two Sum

Easy Problem 1 of 151 Java and Python

Problem

You are given an array of integers nums and an integer target. Return the indices of the two numbers that add up to target.

Every input has exactly one answer, and you may not use the same element twice. The two indices can be returned in any order.

Example 1

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Why: nums[0] + nums[1] = 2 + 7 = 9.

Example 2

Input: nums = [3, 2, 4], target = 6
Output: [1, 2]
Why: nums[1] + nums[2] = 2 + 4 = 6. Index 0 cannot be used twice.

Constraints

2 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i], target ≤ 10⁹
Exactly one valid answer exists.

Explanation

For any number x, the number it needs is fixed: target - x. So the question is really "have I already seen target - x, and where?"

Checking every pair answers that slowly. A hash map from value to index answers it in constant time, so a single pass through the array is enough.

Approach 1 · Naive

Check every pair

Time O(n²)
Space O(1)

Try every pair (i, j) with i < j and return the first pair whose sum is target.

Loop i from 0 to n – 1.
Loop j from i + 1 to n – 1.
If nums[i] + nums[j] == target, return [i, j].

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        return new int[0];
    }
}

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

Approach 2 · Optimal

One-pass hash map

Time O(n)
Space O(n)

Walk the array once. Before storing the current number, look up its complement target - nums[i] in a map of numbers seen so far.

Create an empty map from value to index.
For each index i, compute need = target - nums[i].
If need is in the map, return [map[need], i].
Otherwise store nums[i] → i and continue.

Java

import java.util.*;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seen.containsKey(need)) {
                return new int[] { seen.get(need), i };
            }
            seen.put(nums[i], i);
        }
        return new int[0];
    }
}

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for i, num in enumerate(nums):
            need = target - num
            if need in seen:
                return [seen[need], i]
            seen[num] = i
        return []

Complexity compared

Approach	Time	Space
Naive Check every pair	O(n²)	O(1)
Optimal One-pass hash map	O(n)	O(n)

Key takeaways

"Have I seen the value I need?" is a hash map lookup.
Store the current number after the lookup, so an element never pairs with itself.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem