Python Exercise 23: Two sum
Tags: python, beginners, leetcode
Published: 2022-07-16 08:35:58

## Question
- 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
- **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.**

## My attempt
### First attempt
- The algorithm is work theoretical but too slow, run out of time if last two test case
- algorithm

```
> find the indices of the two number such that they add up to target
>>find two number if they add up to the target
  for index1, num1 in the nums:
	  for index2,num2 in the nums:
		  if num2 is not the same number as num1:
			  if value1 + value 2 == target:
				  return a list consist of index1 and index2
```
- code

```python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        final_list = [[index1,index2] for index1,value1 in enumerate(nums) for index2,value2 in enumerate(nums) if index2 > index1 if value1+value2 ==target]
        return final_list[0]

```

### Second attempt (success pass all test)
- algorithm
```
> find the indices of the two number such that they add up to target
>>find two number if they add up to the target
  for index1,value1 in nums:
	  calculate a second_number that have a sum with value equals to target
	  if second is in nums:
		  find the indices of the second_number
		  if the second_number is not the same number as value1:
			  return a list consist of index1 and index2
```
- code
```python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for index1, value1 in enumerate(nums):
            second_number = target - value1
            if second_number in nums:
                second_number_index = nums.index(second_number)
                if second_number_index != index1:
                    return [index1, second_number_index]
```

## Other solution
### Claim to be the fastest algorithm with 0(n) complexity
- algorithm

```
> find the indices of the two number such that they add up to target
 initiate seen as empty dictionary
 for index, value in nums:
	 calculate a second_number that have a sum with value equals to target
	 if second_number is in seen dictionary:
		 return a list of index and the index of second_number
	 if second_number is not in seen:
		 add the value as key and index as value in the seen dictionary
```
- code

```python
class Solution:
   def twoSum(self, nums: List[int], target: int) -> List[int]:
       seen = {}
       for index, value in enumerate(nums):
           second_number = target - value
           
           if remaining in seen:
               return [index, seen[second_number]]
            
           seen[value] = index
```
## My reflection
This is a good challenge to make me think a method that not just rely on for loop completely. And I learn a new pattern form others to use a dictionary to reduce searching time.

## Credit
challenge on [leetcode 1](https://leetcode.com/problems/two-sum/)
solution on [code recipe](https://www.code-recipe.com/post/two-sum)