# Two sum Problem

February 19, 2023

## Introduction

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.

## Approach

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.

## Code

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

## Explanation

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.

## Complexity analysis

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.

## Conclusion

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.