## Problem

- Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

```
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
```

Note:

- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.

## Thought Process

- create a dictionary to store the data where k = data, value = data index
- for num in dictionary, check if target - num exists in the rest of the array, if exist return the index of num and target-num
- the problem assumes each input would have exactly one solution, however just in case there’s no solution return false

### issues

- however, there are issues with this solution, if there are repetitive elements, then we will have collision, the new element will replace the previous element
- the root cause of this issue is bc we put all elements into the hash table all at once, the search can be a dynamic process as below:
- for any given state:
- at index i, we move to value v, all elements before v were moved into the hash table already
- if target - v exists in the hash table, return [i, ht[target-v]]
- else i += 1, so new v will replace the old v, since the problem assumes only 1 solution, we can confirm that:
- [v, v] wont be a solution
- after new v replace old v, it doesn’t matter which v is used for a potential solution that v + w = target
- however, if the problem asks for all the solutions, it requires a different ds, maybe a stack?

## White Board

Below is the white board:

## Code

```
class Solution:
def two_sum(self, nums, target):
res_d = {}
for i in range(len(nums)): #O(n)
substrate = target - nums[i]
if substrate in res_d:
return [i, res_d[substrate]]
else:
res_d[nums[i]] = i
return False
def test():
nums = [3, 3]
target = 6
ts = Solution().two_sum(nums, target)
print(ts)
test()
```

`[1, 0]`

## Complexity

- when move array into a dict, time complexity is O(n); hash table search is O(1); so overall time complexity is O(n)
- Space complexity is O(n), as I created both a dict to store results

## Optimization

This is not an optimization, more of an alternative thinking. If we sort the array first, I can use two pointers, l, r:

- since sorting will destroy the order, so make a copy of nums, nums2: O(n)
- l = 0, r = len(nums) - 1
- while l < r
- if nums[l] + nums[r] == target, return [nums2.index(nums[l]), nums2.index(nums[r])]
- elif nums[l] + nums[r] < target, l += 1
- else r -= 1

```
class Solution2:
def two_sum2(self, nums, target):
nums2 = nums.copy()
nums3 = nums.copy()
nums = sorted(nums)
l, r = 0, len(nums)-1
while l <= r:
if nums[l] + nums[r] == target:
if nums2.index(nums[l]) != nums2.index(nums[r]):
return [nums2.index(nums[l]), nums2.index(nums[r])]
else:
nums3[nums2.index(nums[l])] = None
return [nums2.index(nums[l]), nums3.index(nums[r])]
elif nums[l] + nums[r] < target :
l += 1
else:
r -= 1
return False
def test_two_sum2():
# nums = [2,7,11,15]
# target = 9
nums = [3,2,4]
target = 6
inter = Solution2().two_sum2(nums, target)
print(inter)
test_two_sum2()
```

`[1, 2]`

We need to sort the arrays first, in python the time complexity for sorted method is O(nlogn), space complexity is O(n) as we need additional ds to store the results.