Author: CongranLu

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.

最近打算开始系统化地刷一些Leetcode 的面试题，一方面是为了为自己的quantitative trader / Researcher的职业做准备，另一方面也是为了以后能够在复习的时候有一个更加系统化的索引。

很多时候，自己的思路和能力是很有限的，所以我不仅希望提供自己的思路，我也可能会去读一些别人写的code，去分析他们的思路，并且和自己的思路进行比较，然后可以提升自己的分析code的能力以及一些不一样的思路。

我知道很多事情都是道阻且长，除了自己努力没有别的办法，每天都坚持努力，不管怎么样都应该会变得更好。想到什么事情就要去做。不应该为自己的行为去找任何借口。

陆琮然

01/03/2020

UpDate:

在咨询朋友的建议之后，我决定按照算法得类型来集中练习，不再序号顺序做题。主要还是因为很多算法和数据结构都是需要系统性学习和练习的，集中练习可以比较好地记住这些知识。

15/03/2020

索引：

我打算在这里增加一个索引，对任何有需要的朋友，这个可以更加方便地替你找到你想要的类型的问题。如果有leetcode的小伙伴其实可以直接查看leetcode上的tag然后直接搜索对应的问题即可。

26/03/2020