Question 1 Two Sum

The description of the question is in the following link: https://leetcode.com/problems/two-sum/

//My code:

for i in range(len(nums)-1):
for j in range(i+1,len(nums)):
if (nums[i]+nums[j] == target):
return [i,j]

Explanation:

My idea is to search all the pairs and return the index pair whenever I found the pair. So for the first for loop, I start from the very beginning. For the second for loop, I start from the number due to the symmetry of the sum. It could be modified by returning an empty array if there is no such pair.

// The code from the forum:

    def twoSum(self, num, target):
        map = {}
        for i in range(len(num)):
            if num[i] not in map:
                map[target - num[i]] = i + 1
            else:
                return map[num[i]], i + 1

        return -1, -1

This uses the idea called “Hash Table”. It is a dictionary, however, the key of the Hash Table is a function of the input value, and then we save it in the RAM and we are able to obtain it whenever we want.

Back to this example. For each value num[i], we want to know if it corresponds to a specific value in the hash table we construct. For example, for the index 0, the table is empty, thus we definitely want to save the value (target – num[0]) into the dictionary and gives a value for the key as the index. So if for the first time, the element num[i] is in the dictionary, corresponding to the element num[j],  and the index we stored for the (target -num[j]) in the dictionary is j + 1 (as the starting number in python is 0).

Summary:

  1. Going through all the pairs is the basic idea of finding things, however, the enumeration is not the best and the most efficient way to do it, because it may waste some the computational power and does not make full use of the space capacity.
  2. Ideas for the Hash Table in this case:
    1. We have the relation of two things: e.g. a+b = k, k is a constant. or b = f(a)
    2. We want to output the value a and b.
    3. We store the dictionary element {f(a) = b: a}
    4. If the ith element num[i-1] gives the value b we want, then we may output num[i-1] and a for these two pairs.

These are the main explanations for these two ideas. There is definitely more things for the Hash Table to learn.

Leave a comment