# 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 **_exactly_ one solution**, and you may not use the _same_ element twice.
You can return the answer in any order.
# Solution
## Naive Solution
The naive solution would of course be two nested loops:
If for every number in our list we check every other number in the list, we can find the answer in quadratic time:
```python
for i in range(len(nums)):
for j in range(len(nums)):
if i==j: continue
if nums[i] + nums[j] == target:
return [i,j]
```
Time Complexity: O$(n^2)$ | Space Complexity: O$(1)$
## Optimized Solution
This problem can be solved in linear time by introducing a [[dictionary]] which will store the last seen index of each number. Then, for each `num` in our list as we iterate, we compute the `complement`, which satisfies `num + complement == target`. If `complement` is a key in our [[dictionary]], we return the two indices. Else, we store the index of `num`.
```python
lastIndex = {}
for i, num in enumerate(nums):
complement = target - num
if complement in lastIndex:
return [i, lastIndex[complement]]
lastIndex[num] = i
```
Time Complexity: O$(n)$ | Space Complexity: O$(n)$