Intuition

Use HashMap to keep numbers and their indices we found.

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)

Copy

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"]

Copy

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"]

Copy

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

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

Copy

Approach

1. 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.
2. If the current number is already in the HashMap, return the index of the current number and the index stored in the HashMap.
3. We still need to return an empty array if there is no solution.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Code

Golang

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{}
}

Python

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 []

C++

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