# [LC] 1. Two Sum

https://leetcode.com/problems/two-sum/

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

## Thoughts

There is probably a bunch of solution since it is a most famous problem in LC. First, I may compare every two pairs like brute force. For example, loop 1 will select one number indexed by i, and the inner loop will cover another one number indexed by j and i!=j. Then we can compare nums[i] +nums[j] = target. In that case, the time complexity is \$latex O(N^2)\$ So, it’s not a good idea.

Another solution can be made by a two-pointer. We can first sort array and have a two-pointer i=num and j=num[n]. Then we can compare num[i]+num[j]. Let says the sum of them is k, then we should find k == target. If k is less than a target, we increase i since num[i] is the smallest number so far. If k is larger than a target, we decrease j since num[j] is the largest number. Likewise, we keep continuing this procedure until i >= j. In that case, the time complexity is O(NlogN) since we need sorting.

Can we do more better? Maybe there is a single loop solution if we loop the array in a constant N time. We know that in the sense of Big-O notation, 2N or 3N all those are the same as O(N). So, maybe we can use this character. Then, let’s think about a + b = target. How about we first calculate some information, store it, and use it for the next calculation? a + b = target means a = target – b. So, first, we can save all target – b in map[target-b], and in the next loop we can simply check whether there is a map[a] or not since target – b = a.

``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# a + b = target, a = target - b
# first insert all target - b in map valued as index no
# second, find if a exist in b if not equal index

d = collections.defaultdict(int)
for i, num in enumerate(nums):
d[target - num] = i

for i, num in enumerate(nums):
if num in d and d[num] != i:
return [i, d[num]]
return []``````

Submission

Runtime: 52 ms, faster than 26.98% of Python3 online submissions for Two Sum.Memory Usage: 14.6 MB, less than 13.36% of Python3 online submissions for Two Sum.

In this case, both time and space complexity is O(N)