Skip to content

[leetcode] 1. Two Sum

Published: at 02:39 AM (2 min read)

Description

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:


Approach

Given the following assumptions:

We can use a Map to keep track of the numbers we have traversed.

During the traversal, we check if there is a matching number(complement) in the Map. If there is, it is the correct answer.

Solution

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (numbers, target) {
  // Create a map to store the indices of the numbers we've seen so far
  const indexMap = {};

  for (let currentIndex = 0; currentIndex < numbers.length; currentIndex++) {
    // Calculate the complement that would add up to the target with the current number
    const complement = target - numbers[currentIndex];

    // Check if the complement exists in the map
    if (indexMap.hasOwnProperty(complement)) {
      // If it exists, return the indices of the complement and the current number
      return [indexMap[complement], currentIndex];
    }

    // Otherwise, add the current number and its index to the map
    indexMap[numbers[currentIndex]] = currentIndex;
  }

  // If no solution is found, return an empty array (although the problem guarantees one solution)
  return [];
};

Complexity Analysis

Time Complexity

The time complexity is O(n) because we traverse the array once.

Space Complexity

The space complexity is O(n) because we store the indices of the numbers in the map.