## Table of contents

## Open Table of contents

## Problem

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 <= 104`

`-109 <= nums[i] <= 109`

`109 <= target <= 109`

**Only one valid answer exists.**

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

## Explanation/Approach

This problem requires finding two numbers from the given array that add up to the target. We have several ways to approach this problem.

**Brute Force:**We can iterate over the array with two loops and check all possible pairs. If a pair adds up to the target, we return the indices. This approach is straightforward but not efficient.**Two-pass Hash Table:**This approach involves two iterations. In the first, we add each element’s value and its index to the hash table. In the second, for each element, we check if the hash table contains the complement (target - current element). If it does, and it’s not the same element, we found the solution.**One-pass Hash Table:**This approach improves the Two-pass Hash Table method by checking and adding elements to the hash table in the same iteration. For each element, we check if its complement is in the table before adding the current element to the table.

## Solution 1: Brute Force

```
class Solution:
def two_sum(self, nums: List[int], target: int) -> List[int]:
# Get the length of the list
num_count = len(nums)
# Iterate over the list with two nested loops
for i in range(num_count - 1):
for j in range(i + 1, num_count):
# If a pair adds up to the target, return the indices
if nums[i] + nums[j] == target:
return [i, j]
return [] # No solution found
```

**Time and Memory Complexity**

The time complexity is O(n^2) as there are two nested loops over the array. The space complexity is O(1) as no additional space is required.

**Explanation**

The solution iterates over the list with two nested loops. For every pair of numbers, it checks if they add up to the target. If they do, it immediately returns the indices. If no pair adds up to the target, it returns an empty list.

## Solution 2: Two-pass Hash Table

```
class Solution:
def two_sum(self, nums: List[int], target: int) -> List[int]:
# Create an empty hash table
num_map = {}
num_count = len(nums)
# First pass: build the hash table
for i in range(num_count):
num_map[nums[i]] = i
# Second pass: find the complement
for i in range(num_count):
complement = target - nums[i]
if complement in num_map and num_map[complement] != i:
return [i, num_map[complement]]
return [] # No solution found
```

**Time and Memory Complexity**

The time complexity is O(n) as we traverse the array twice. The space complexity is O(n) as we need a hash table to store n elements.

**Explanation**

In the first pass, we add every number and its index to the hash table. In the second pass, we look for each number’s complement in the hash table. If we find it, and it’s not the same number, we return the indices.

## Solution 3: One-pass Hash Table

```
class Solution:
def two_sum(self, nums: List[int], target: int) -> List[int]:
# Create an empty hash table
num_map = {}
num_count = len(nums)
# Single pass: find the complement and add the number to the hash table
for i in range(num_count):
complement = target - nums[i]
if complement in num_map:
return [num_map[complement], i]
num_map[nums[i]] = i
return [] # No solution found
```

**Time and Memory Complexity**

The time complexity is O(n) as we traverse the array once. The space complexity is O(n) as we need a hash table to store n elements.

**Explanation**

This solution is an improvement over the two-pass hash table. For every number, it checks if its complement is in the hash table before adding the number to the table. If the complement is found, it returns the indices.