1-TwoSum

## 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 + nums = 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.

Reprint policy 20-Valid-Parentheses 十大经典排序算法整理汇总（附代码）