Two Sum

Published: Aug 15, 2024

Easy Array Hash Table

Problem 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.

Constraints:

  • - 2 <= nums.length <= 10**4
  • -10**9 <= nums[i] <= 10**9
  • -10**9 <= target <= 10**9
  • Only one valid answer exists.

Examples

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]

How to Solve

This is very basic algorithm question which uses a hash table. Save a pair of target - nums[i] as key and index as value in the hash table. If nums[i] is in the hash table, a result is found. So, return the pair of nums[i]’s value and a current index.

Solution

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

class TwoSum {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
            int tmp = target - nums[i];
            if (m.find(tmp) != m.end()) {
                return {m[tmp], i};
            } else {
                m.insert({nums[i], i});
            }
        }
        return {-1, -1};
    }
};

import java.util.HashMap;
import java.util.Map;

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

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const m = {};
    for (let i = 0; i < nums.length; ++i) {
        if (String(nums[i]) in m) {
            return [m[String(nums[i])], i];
        } else {
            m[target - nums[i]] = i;
        }
    }
    return [-1, -1];
};

class TwoSum:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = {}
        for i in range(len(nums)):
            if nums[i] in d:
                return [d[nums[i]], i]
            else:
                d[target - nums[i]] = i

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
    h = {}
    nums.each_with_index do |num, idx|
        if h.has_key?(num)
            return [h[num], idx]
        else
            h[target - num] = idx
        end
    end
    [-1, -1]
end

Complexities

  • Time: O(n)
  • Space: O(n)