Two Sum
On this page 
Problem Statement Solution 1: Using a Hash Map Solution 2: Using a Nested Loop Solution 3: Using a Single Pass with Map Solution 4: Using Array.prototype.findIndex() Solution 5: Using Two-Pointer Technique (Sorted Array) Solution 6: Using Array.prototype.reduce() Solution 7: Using a Map with a Custom Object Solution 8: Using a Set for Seen Values Solution 9: Using Array.prototype.indexOf() for Lookup Solution 10: Using a Binary Search Approach (Requires Sorted Array) Solution 11: Using Array.prototype.forEach() Solution 12: Using Array.prototype.some() Solution 13: Using Array.prototype.map() and Array.prototype.find() Solution 14: Using a Generator Function Solution 15: Using Array.prototype.filter() Solution 16: Using Array.prototype.map() and Index Lookup Resources Frequently asked questions More Problems Solutions
Problem Statement
You are given an array of integers, nums, and an integer, target. Your task is to find the indices of the two numbers in the array that add up to the given target. You can assume that each input will have exactly one solution, and you may not use the same element more than once. The order of the indices in the output does not matter.
Example 1
Input: array = [2,7,11,15] , target = 9
Output: [0,1]
Example 2
Input: array = [3,2,4] , target = 6
Output: [1,2]
Example 3
Input: array = [3,3] , target = 6
Output: [0,1]
Constraints
The length of
numswill be between 2 and 10410^4104.Each integer in
numsandtargetwill be between −109-10^9−109 and 10910^9109.There is exactly one solution for each input, and no element will be used more than once.
Solution 1: Using a Hash Map
function twoSumHashMap(nums, target) {
const numToIndex = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (numToIndex.has(complement)) {
return [numToIndex.get(complement), i];
}
numToIndex.set(nums[i], i);
}
return [];
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumHashMap(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumHashMap(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumHashMap(array3,target3); //output: [0,1]
Solution 2: Using a Nested Loop
function twoSumNestedLoop(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
return [];
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumNestedLoop(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumNestedLoop(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumNestedLoop(array3,target3); //output: [0,1]
Solution 3: Using a Single Pass with Map
function twoSumSinglePass(nums, target) {
const indexMap = {};
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (indexMap[complement] !== undefined) {
return [indexMap[complement], i];
}
indexMap[nums[i]] = i;
}
return [];
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumSinglePass(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumSinglePass(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumSinglePass(array3,target3); //output: [0,1]
Solution 4: Using Array.prototype.findIndex()
function twoSumFindIndex(nums, target) {
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
const complementIndex = nums.slice(i + 1).findIndex(num => num === complement);
if (complementIndex !== -1) {
return [i, i + 1 + complementIndex];
}
}
return [];
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumFindIndex(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumFindIndex(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumFindIndex(array3,target3); //output: [0,1]
Solution 5: Using Two-Pointer Technique (Sorted Array)
function twoSumTwoPointer(nums, target) {
const sortedNums = nums.map((num, index) => ({ num, index })).sort((a, b) => a.num - b.num);
let left = 0;
let right = sortedNums.length - 1;
while (left < right) {
const sum = sortedNums[left].num + sortedNums[right].num;
if (sum === target) {
return [sortedNums[left].index, sortedNums[right].index];
} else if (sum < target) {
left++;
} else {
right--;
}
}
return [];
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumTwoPointer(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumTwoPointer(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumTwoPointer(array3,target3); //output: [0,1]
Solution 6: Using Array.prototype.reduce()
function twoSumReduce(nums, target) {
const seen = {};
return nums.reduce((result, num, index) => {
const complement = target - num;
if (complement in seen) {
result = [seen[complement], index];
}
seen[num] = index;
return result;
}, []);
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumReduce(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumReduce(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumReduce(array3,target3); //output: [0,1]
Solution 7: Using a Map with a Custom Object
function twoSumMapObject(nums, target) {
const indexMap = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (indexMap.has(complement)) {
return [indexMap.get(complement), i];
}
indexMap.set(nums[i], i);
}
return [];
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumMapObject(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumMapObject(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumMapObject(array3,target3); //output: [0,1]
Solution 8: Using a Set for Seen Values
function twoSumSet(nums, target) {
const seen = new Set();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) {
return [nums.indexOf(complement), i];
}
seen.add(nums[i]);
}
return [];
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumSet(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumSet(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumSet(array3,target3); //output: [0,1]
Solution 9: Using Array.prototype.indexOf() for Lookup
function twoSumIndexOf(nums, target) {
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
const complementIndex = nums.indexOf(complement, i + 1);
if (complementIndex !== -1) {
return [i, complementIndex];
}
}
return [];
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumIndexOf(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumIndexOf(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumIndexOf(array3,target3); //output: [0,1]
Solution 10: Using a Binary Search Approach (Requires Sorted Array)
function twoSumBinarySearch(nums, target) {
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
const complementIndex = binarySearch(nums, complement, i + 1);
if (complementIndex !== -1) {
return [i, complementIndex];
}
}
return [];
}
function binarySearch(arr, target, start) {
let left = start;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumBinarySearch(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumBinarySearch(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumBinarySearch(array3,target3); //output: [0,1]
Solution 11: Using Array.prototype.forEach()
function twoSumForEach(nums, target) {
const indexMap = {};
let result = [];
nums.forEach((num, i) => {
const complement = target - num;
if (indexMap[complement] !== undefined) {
result = [indexMap[complement], i];
}
indexMap[num] = i;
});
return result;
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumForEach(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumForEach(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumForEach(array3,target3); //output: [0,1]
Solution 12: Using Array.prototype.some()
function twoSumSome(nums, target) {
let result = [];
nums.some((num, i) => {
const complement = target - num;
const index = nums.slice(i + 1).indexOf(complement);
if (index !== -1) {
result = [i, i + 1 + index];
return true; // Exit early when found
}
return false;
});
return result;
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumSome(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumSome(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumSome(array3,target3); //output: [0,1]
Solution 13: Using Array.prototype.map() and Array.prototype.find()
function twoSumMapFind(nums, target) {
const numMap = nums.map((num, i) => ({ num, index: i }));
for (let i = 0; i < numMap.length; i++) {
const complement = target - numMap[i].num;
const complementObj = numMap.find(obj => obj.num === complement && obj.index !== numMap[i].index);
if (complementObj) {
return [numMap[i].index, complementObj.index];
}
}
return [];
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumMapFind(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumMapFind(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumMapFind(array3,target3); //output: [0,1]
Solution 14: Using a Generator Function
function twoSumGenerator(nums, target) {
for (const [i, j] of generatePairs(nums)) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
return [];
}
function* generatePairs(nums) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
yield [i, j];
}
}
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumGenerator(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumGenerator(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumGenerator(array3,target3); //output: [0,1]
Solution 15: Using Array.prototype.filter()
function twoSumFilter(nums, target) {
const indices = nums.map((num, i) => i);
for (let i = 0; i < indices.length; i++) {
const firstIndex = indices[i];
const complement = target - nums[firstIndex];
const secondIndex = indices.slice(i + 1).find(idx => nums[idx] === complement);
if (secondIndex !== undefined) {
return [firstIndex, indices.indexOf(secondIndex, i + 1)];
}
}
return [];
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumFilter(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumFilter(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumFilter(array3,target3); //output: [0,1]
Solution 16: Using Array.prototype.map() and Index Lookup
function twoSumMapLookup(nums, target) {
const numToIndex = nums.reduce((acc, num, i) => {
acc[num] = i;
return acc;
}, {});
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (numToIndex.hasOwnProperty(complement) && numToIndex[complement] !== i) {
return [i, numToIndex[complement]];
}
}
return [];
}
const array1 = [2,7,11,15];
const target1 = 9;
twoSumMapLookup(array1,target1); //output: [0,1]
const array2 = [3,2,4];
const target2 = 6;
twoSumMapLookup(array2,target2); //output: [1,2]
const array3 = [3,3];
const target3 = 6;
twoSumMapLookup(array3,target3); //output: [0,1]
Resources
Frequently asked questions
What if the array is sorted?
If the array is sorted, you can use more efficient methods like the two-pointer technique to find the solution. However, sorting the array might alter the original indices, so ensure you track the original indices if needed.
Can the "Two Sum" problem be solved in constant space?
No, solving the "Two Sum" problem generally requires additional space to keep track of previously seen numbers. The hash map approach, for example, uses extra space proportional to the number of elements in the array.