Two Sum Easy 0 attempts
Daily LeetCode ↗

Two Sum

Easy ArrayHash Table LeetCode

You're given an array of integers nums and a target value target. Find two different elements in the array whose values add up to target, and return their indices.

Exactly one valid pair exists for any given input, and you can't use the same element twice. The two indices can be returned in either order.

Input Format
Implement twoSum(nums, target). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. Any result satisfying the statement is accepted.

Sample Input and Output

Example 1 · Run Sample

Input
nums = [2,7,11,15]
target = 9
Output
[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 <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • Only one valid answer exists.
Follow-up
  • What if the input array is sorted? (Can you do it in O(1) space?)
  • What if you need to return the values instead of indices?
Test Cases (3)
Case 1
Args: [[2,7,11,15],9] Expected: [0,1]
Case 2
Args: [[3,2,4],6] Expected: [1,2]
Case 3
Args: [[3,3],6] Expected: [0,1]
Topics
ArrayHash Table

Approach: Hash Map

For each number, check if target - num exists in a map of value → index. If it does, return the two indices. Otherwise store the current value and its index.

javascript
function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (map.has(need)) return [map.get(need), i];
    map.set(nums[i], i);
  }
  return [];
}

Time: O(n), Space: O(n).

Saved in this browser only. Private to you.

JavaScript