Two Sum

• easy
• 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 {};
    }
};

Java

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> memory = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            int num = nums[i];
            int complement = target - num;
            if (memory.containsKey(complement)) {
                return new int[]{memory.get(complement), i};
            }
            memory.put(num, i);
        }
        return new int[]{};
    }
}