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 targetnum
 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[targetv]]
 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.