Two Sum

Loading...LeetCode

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.

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 <= 104

• -109 <= nums[i] <= 109

• -109 <= target <= 109

• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Solution:

You can achieve less than O(n^2) time complexity using a hashmap (JavaScript object) to store the indices of previously visited numbers while iterating through the array.

Here's how you can do it:

function twoSum(nums, target) {
    const numMap = {}; // HashMap to store indices of visited numbers
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        // If complement exists in numMap, return indices
        if (numMap.hasOwnProperty(complement)) {
            return [numMap[complement], i];
        }
        
        // Store current number's index in numMap
        numMap[nums[i]] = i;
    }
    
    // No solution found
    return [];
}

// Test cases
console.log(twoSum([2,7,11,15], 9)); // Output: [0, 1]
console.log(twoSum([3,2,4], 6));      // Output: [1, 2]
console.log(twoSum([3,3], 6));        // Output: [0, 1]

This algorithm has a time complexity of O(n) because the lookup time in a hashmap is constant on average, resulting in a significant improvement over the brute force O(n^2) solution.