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.
Input: array = [2,7,11,15] , target = 9
Output: [0,1]
Input: array = [3,2,4] , target = 6
Output: [1,2]
Input: array = [3,3] , target = 6
Output: [0,1]
The length of nums will be between 2 and 10410^4104.
Each integer in nums and target will 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.
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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]
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.
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.