Two Sum

• easy
• hash table
• Problem URL

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.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Solution

Use a key-value store to record the index of each element in nums as we iterate through the array. For each element, check if the store contains the difference between the current element and the target. If it does, we return the current index and the index of the difference. If it doesn’t, we add the current element to the key-value store.

Implementation

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const m = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (m.has(nums[i])) return [m.get(nums[i]), i];
    m.set(target - nums[i], i);
  }
};

TypeScript

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

Go

func twoSum(nums []int, target int) []int {
  m := make(map[int]int)
  for i, num := range nums {
    if idx, ok := m[num]; ok {
      return []int{idx, i}
    }
    m[target-num] = i
  }
  return nil
}

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        m = {}
        for i, num in enumerate(nums):
            if m.get(num) is not None:
                return [m.get(num), i]
            m[target - num] = i

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int, int> memory;
        for (int i = 0; i < nums.size(); ++i) {
            int num = nums[i];
            int complement = target - num;
            if (memory.contains(complement)) {
                return {memory[complement], i};
            }
            memory[num] = i;
        }
        return {};
    }
};

Pseudocode

1. Initialize a key-value store to record the index of each element in nums.
2. Iterate through nums and for each element, check if the key-value store contains the difference between the current element and the target.
3. If it does, return the current index and the index of the difference.

Complexity Analysis

• The time complexity of this algorithm is O(n) because we iterate through the array once.
• The space complexity of this algorithm is O(n) because we store the index of each element in a key-value store.