Link:: https://leetcode.com/problems/two-sum/
up:: [[Leetcode MOC]]
## 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`
- `-10e9 <= nums[i] <= 10e9`
- `-10e9 <= target <= 10e9`
- **Only one valid answer exists.**
**Follow-up:** Can you come up with an algorithm that is less than $O(n^2)$ time complexity?
## Solution
My first attempt will use a nested for loop, at each outer loop iteration, calculate the required complement for that number, then try to find it in the rest of the list. The lists aren't sorted, which makes it more difficult.
After that, I'll think about using a dictionary to cache values and indexes(?) for a speedup.
Then I will work on a faster than $O(n^2)$ solution.
I think the faster solution is to use a dictionary. As you iterate once through the array, add the value: idx to a dictionary, and check dictionary for presence of complement. Only need to iterate once.
### Mine
#### Python
Brute force (nested loops):
```python
def twoSum(self, nums: List[int], target: int) -> List[int]:
for idx, i in enumerate(nums):
complement = target - i
for jdx, j in enumerate(nums[idx+1:]):
if j == complement:
return [idx, jdx+idx+1]
```
Single pass:
```python
def twoSum(self, nums: List[int], target: int) -> List[int]:
d = {}
for idx, i in enumerate(nums):
complement = target - i
if d.get(complement) is not None:
return [idx, d[complement]]
if not d.get(i):
d[i] = idx
```
#### Rust
Nested loops
```rust
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
// let mut i = 0;
// let mut j = 0;
for (idx, i) in nums.iter().enumerate() {
let complement = target - i;
for (jdx, j) in nums[idx+1..].iter().enumerate() {
if *j == complement {
return vec![idx as i32, (idx+jdx+1) as i32]
}
}
}
}
}
```
**NOTE** this isn't complete yet
### LC's
## Things I Learned
## Scratchpad