LeetCode 0001. Two Sum - Hash Map Solution | Go, Python, C++

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:

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?

Intuition

Use HashMap to keep numbers and their indices we found.

Note

Create a Hash Table in GO with make function ^{Golang Maps}, and use map[key] = value to set the value of the key.

numMap := make(map[int]int)

Note

How to Work with maps? ^{Go maps in action#Working with maps}

A two-value assignment tests for the existence of a key:

i, ok := m["route"]

In this statement, the first value (i) is assigned the value stored under the key “route”. If that key doesn’t exist, i is the value type’s zero value (0). The second value (ok) is a bool that is true if the key exists in the map, and false if not.

To test for a key without retrieving the value, use an underscore in place of the first value:

_, ok := m["route"] 

To iterate over the contents of a map, use the range keyword:

for key, value := range m {
    fmt.Println("Key:", key, "Value:", value)
}

Approach

Traverse the nums array and store the difference between the target and the current number as the key and the index as the value in the HashMap.
If the current number is already in the HashMap, return the index of the current number and the index stored in the HashMap.
We still need to return an empty array if there is no solution.

Complexity

Time complexity:
Space complexity:

Code

func twoSum(nums []int, target int) []int {
    hashMap := make(map[int]int)

    for i, num := range nums {
        if j, ok := hashMap[num]; ok {
            return []int{j, i}
        }
        hashMap[target - num] = i
    }

    return []int{}
}

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

        return []

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashMap;

        for (int i = 0; i < nums.size(); ++i) {
            int num = nums[i];
            if (hashMap.find(num) != hashMap.end()) {
                return {hashMap[num], i};
            }
            hashMap[target - num] = i;
        }

        return {};
    }
};

Hugo's Blog