Two Sum

easy
Arrays & HashingArrayHash Table

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.

Examples

Example 1

  • Input: nums = [2,7,11,15], target = 9
  • Output: [0,1]
  • Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2

  • Input: nums = [3,2,4], target = 6
  • Output: [1,2]

Example 3

  • Input: nums = [3,3], target = 6
  • Output: [0,1]

Constraints

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Only one valid answer exists.

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Brute Force

Intuition

The most straightforward approach is to check every possible pair of numbers in the array. For each element, we look at every other element that comes after it to see if their sum equals the target. While this is inefficient, it requires no extra space and is easy to understand. This approach works because we exhaustively search all pairs, guaranteeing we find the answer if it exists.

Algorithm

  1. Iterate through each element nums[i] using an outer loop from index 0 to n-2.
  2. For each nums[i], iterate through every subsequent element nums[j] using an inner loop from index i+1 to n-1.
  3. Check if nums[i] + nums[j] equals the target.
  4. If a match is found, return the pair of indices [i, j].
TimeO(n^2)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};
Java 21
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[] {};
    }
}
Python 3.12
def twoSum(nums: list[int], target: int) -> list[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []
Go 1.26
func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i]+nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return []int{}
}
Approach 2

Hash Map

Intuition

Instead of checking every pair, we can trade space for time by using a hash map. The key insight is that for each number x, we are looking for its complement target - x. As we iterate through the array, we store each number and its index in a hash map. Before inserting a new number, we check if its complement already exists in the map. If it does, we have found our pair. This is a single-pass approach because we look up and insert in the same traversal.

Algorithm

  1. Create an empty hash map to store each number and its index.
  2. Iterate through the array. For each element nums[i], compute the complement: complement = target - nums[i].
  3. Check if the complement already exists in the hash map.
  4. If the complement is found, return [map[complement], i] -- the stored index of the complement and the current index.
  5. If the complement is not found, add nums[i] -> i to the hash map and continue.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;

        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];

            if (map.count(complement)) {
                return {map[complement], i};
            }

            map[nums[i]] = i;
        }

        return {};
    }
};
Java 21
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> 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);
        }

        return new int[] {};
    }
}
Python 3.12
def twoSum(nums: list[int], target: int) -> list[int]:
    seen = {}

    for i, num in enumerate(nums):
        complement = target - num

        if complement in seen:
            return [seen[complement], i]

        seen[num] = i

    return []
Go 1.26
func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, num := range nums {
        complement := target - num
        if j, ok := m[complement]; ok {
            return []int{j, i}
        }
        m[num] = i
    }
    return []int{}
}

Frequently asked questions

What is the optimal time complexity of Two Sum?

The most efficient approach in this guide ("Hash Map") runs in O(n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Two Sum use?

Two Sum is a easy-level Arrays & Hashing problem involving Array, Hash Table. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Two Sum be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Contains Duplicate

Original problem: leetcode.com

Loading editor...
Input
nums=
[2,7,11,15]
target=
9
Expected Output
[0,1]