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].
问题是输入一个数组，找到其中两个相加等于target的数的下标，并且这样一个数组中只存在一对这样的数据，这大大降低的问题的难度。
知识点：
1. 指针函数
2. malloc和free函数---动态分配内存
3. 哈希表
知识点分析：
1. 代码里首先给出了int*，说明函数返回的是一个int类型的指针，所以在函数中的返回值必须声明为int型指针
2. 编程时如果知道数组的大小，则可以将内存分配写死，但是如果在编程时不知道数组的大小，或者说数组的大小是可变的并且变化范围很大，那么这个时候将内存分配写死就会造成资源的浪费，所以可以使用malloc来按需分配内存，然后在程序结束后用free函数释放内存。
void *malloc(int num); void free(void *address); 因为malloc分配内存是没有类型的，所以可以在分配后进行强制类型转换，代码中malloc前的（int*） 3. 在分析这道题的时候首先想到的是穷举法，先对第一个数据进行遍历匹配，在对第二个数据进行遍历匹配，需要的循环时间是n!。但是这个方法效率太低，时间复杂度为O(N^2)，leetcode好像不会接收这种算法。那么可以用空间换时间的办法来完成这道题，及消耗更多的内存，减少程序运行时间。遍历查找 ----> 直接查找 找到即停止（因为数组中只有一对数据符合要求）
算法的思路是：
先初始化哈希表的值为-1，
然后也是从i = 0；循环到 i = num是Size - 1，每次循环做两个事情：
1. 将数据num[i]插入哈希表中，num[i]作为表的下标，i作为表的值，哈希表其实也是一个数组；
2. 判断table[target - num[i]] 是否等于-1，若不等于，则table[target - num[i]] 和 i 就是要找的下标。
注：第二步要在第一步之前，这样写是为了便于理解。
哈希表相当于是将整个数组作为了table的下标，通过数据反过来查下标，查找过程如下：
我们首先假设两个数据的下标是x和y，x < y，对应的数据为X和Y，即有X + Y = target，X = target - Y。
1. 在循环到 i= x 时，x的数据首先被写入了table，即table[X] = x，因为x为数组的下标，它的值是大于等于0的，不可能等于-1；
2. 在循环到 i = y时，table[target - Y] = table[X] = x，不等于-1，break，结束查找。
哈希表缺点：
初始化哈希表时需要给它分配内存，如果输入数组为[1, 2, 2000]，那么table的大小就是2000，需要巨大的内存空间，而事实上此时只有3个数据，当然时间复杂度并没有变化。
对以上算法的改进：
如文中最后的代码所示，先找出数组的最小值min和满足target要求的最大值max，这样哈希表的大小就变成了len = max - min + 1，这样增加了N的时间复杂度，但是会大量减少空间复杂度，而事实上时间复杂度还是O(N).
思考：
是不是有其他的表，最大空间就是数组大小的空间。
/** * Note: The returned array must be malloced, assume caller calls free(). */ int* twoSum(int* nums, int numsSize, int target) { int i = 0; int min; min = nums[0]; for (i = 0; i < numsSize; i++) { if (nums[i] < min) min = nums[i]; } int max = target - min; int len = max - min + 1; int *table = (int*)malloc(len*sizeof(int)); int *index = (int*)malloc(2*sizeof(int)); if (table == NULL) { exit(1); } for (i = 0; i < len; i++) { table[i] = -1; } for (i = 0; i < numsSize; i++) { if (nums[i] <= max) { if (table[target - nums[i] - min] != -1) { index[0] = table[target - nums[i] - min]; index[1] = i; break; } table[nums[i] -min] = i; } } free(table); return index; } 我们首先假设两个数据的下标是x和y
