# Two Sum

The task is to find two numbers in an array that add up to a specific target.

You can find the original problem described on LeetCode.

## Problem Statement

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

**, and you may not use the**

*exactly*one solution*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.

## Problem Solving

### A brute force solution

There is a simple method to solve this problem:

Use two `for`

*loops* to iterate through the elements and find the combination.

```
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
for i in 0..<nums.count {
for j in (i + 1)..<nums.count {
if nums[i] + nums[j] == target {
return [i, j]
}
}
}
return []
}
```

Pretty straight forward and easy to implement, right? ๐

The time complexity for this solution is `O(nยฒ)`

.

However, this is definitely not a good solution. ๐

### Hash Table

A good solution is to use a *hash table* (here we use Swift’s `Dictionary`

) to store the numbers we have seen so far and their corresponding indices. This way, we can check in constant time if the complement of the current number (*target - current number*) exists in the hash table.

Here, let me show you. ๐จโ๐ซ

```
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
// Store the number and its index
var dictionary: [Int: Int] = [:]
for (i, num) in nums.enumerated() {
// Check if the complement (target - num) is already in the dictionary
if let item = dictionary[target - num] {
// If found, return the indices
return [item, i]
}
// Store the current number and its index
dictionary[num] = i
}
// Corner case (the problem states there must be a solution)
return []
}
```

## Complexity Analysis

### Time Complexity

As mentioned before, the first solution has time complexity `O(nยฒ)`

, where `n`

is the number of elements in the array.

The time complexity for the second solution is `O(n)`

. We traverse the list containing `n`

elements exactly once, and each lookup in the dictionary costs `O(1)`

time.

### Space Complexity

The space complexity of the first solution is `O(1)`

since we do not create any extra space and return the indexs of the existing arrays.

The second solution, even though is better, in terms of time complexity, it costs `O(n)`

space. The extra space required depends on the number of items stored in the dictionary, which stores at most `n`

elements.

## Conclusion

The solution here demonstrates the use of hash tables for efficient lookups.

This approach ensures a linear time complexity, making it highly efficient for large inputs. ๐ค

**Check all problem solutions and run the test cases easily with LeetSwift! ๐**

**Get fresh, exclusive content delivered right to your inbox every week ๐ฌโจ**