Two Sum
Find 2 numbers in the array that add up to the target sum.
Easy
Difficulty
O(n)
Time Complexity
O(n)
Space Complexity
HashMap
Approach
Jan 18, 2026
Last Updated
Problem Statement
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]
Mathematical Approach
For each element in the array, we need to find if there exists another element such that: This can be rewritten as:
If is nums[i], then becomes the complement of nums[i].
Brute Force Approach
The brute force approach for this problem would be to go through each element in the array
nums[i], and have a nested loop that starts from nums[i+1], and check to find combinations that add up to the target. Two Sum - Brute Force Approach
Two Sum - Brute Force Approach
1class TwoSum {
2 public int[] twoSum(int[] nums, int target) {
3
4 for (int i=0; i< nums.length; i++){
5 for (int j=i+1; j<nums.length; j++){
6 if (nums[i]+nums[j] == target){
7 return new int[]{i, j};
8 }
9 }
10 }
11 return new int[]{-1, -1};
12
13 }
14}Complexity Analysis
Time Complexity
Brute Force: O(n^2)
Space Complexity
Brute Force: O(1)
Optimal Approach using Hashmap
To improve the time complexity, we can use hashmaps. With this approach, we only need to loop through the array items once.
To do this, we initialize an empty hashmap. As we loop through the elements, we first find the complement of the current number. Then we check if this complement already exists in the hashmap.
If the complement does NOT exist, we save the current number as the key, and it's index as the value into the hashmap.
If it does exist, we return the current index and the index of the complement, stored as the complement's value in the hashmap, as a new array.
To do this, we initialize an empty hashmap. As we loop through the elements, we first find the complement of the current number. Then we check if this complement already exists in the hashmap.
If the complement does NOT exist, we save the current number as the key, and it's index as the value into the hashmap.
If it does exist, we return the current index and the index of the complement, stored as the complement's value in the hashmap, as a new array.
Two Sum - HashMap Approach
Two Sum - HashMap Approach
1class Solution {
2 public int[] twoSum(int[] nums, int target) {
3
4 HashMap<Integer, Integer> map = new HashMap<>();
5 int complement;
6
7 for (int i=0; i<nums.length; i++){
8 complement = target - nums[i];
9
10 if (map.containsKey(complement)){
11 return new int[]{i, map.get(complement)};
12 }
13 else{
14 map.put(nums[i],i);
15 }
16 }
17
18 return new int[]{-1, -1};
19
20 }
21}Step-by-Step Walkthrough
Let's trace through example 1: [2, 7, 11, 15], target = 9
1
HashMap is initialized as empty = {}
2
First element = nums[0] = 2
3
Complement of 2 for target 9 would be 7
4
Check if 7 exists in the hashmap => doesn't exist so we add 2 into the hashmap as key and index = 0 as it's value
5
hashmap = { (2:0) }
6
Next element = nums[1] = 7
7
Complement of 7 for target 9 would be 2
8
Check if 2 exists in the hashmap => EXISTS
9
So we return a new array with 2 indices, current index = 1, and the index of the complement = 0
10
return [ 1, 0]
Complexity Analysis
Time Complexity
HashMap: O(n)
Space Complexity
HashMap: O(n)