Two sum Problem

In this post, I’ll be solving the “Two Sum” problem on LeetCode. This problem is a classic example of a problem that can be solved using a hash table, and it’s a great introduction to using hash tables in algorithms. The problem statement is as follows: 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.

To solve this problem, we can use a hash table to store each element of the array along with its index. We can then iterate through the array and for each element, check if the difference between the target and the current element is in the hash table. If it is, we’ve found our two numbers and we can return their indices. If it’s not, we add the current element to the hash table and continue iterating.

Here’s the code to solve the problem using a hash table:

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

The twoSum function takes an array of integers nums and an integer target as input. It initializes an empty hash table called numMap to store each element of the array and its index. It then iterates through the array using a for loop and for each element, it calculates the difference between the target and the current element and stores it in a variable called complement.

It then checks if the complement is in the numMap hash table. If it is, it means that we’ve found our two numbers that add up to the target, so we return their indices in the form of a slice. If it’s not, we add the current element to the numMap hash table along with its index, so that we can look it up later if we need to.

If we iterate through the entire array and don’t find a solution, we return an empty slice, since the problem statement guarantees that there is exactly one solution and we don’t need to handle the case where there is no solution.

Testing: To test our code, we can call the twoSum function with some sample inputs:

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    result := twoSum(nums, target)
    fmt.Println(result)
}

This should output [0 1], since the two numbers that add up to 9 are at indices 0 and 1 in the nums array.

The time complexity of this algorithm is $O(n)$, since we iterate through the entire array once. The space complexity is $O(n)$, since we need to store each element of the array and its index in the hash table.

In this post, we’ve solved the “Two Sum” problem on LeetCode using a hash table. We’ve seen how hash tables can be used to solve problems that involve finding pairs of numbers that add up to a target value.