首页 > 代码库 > Two Sum问题
Two Sum问题
题目描述：
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.
样例：
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
这是我刷leetcode的第一题，读懂题目后，果断采用暴力枚举的办法。
int* twoSum(int* nums, int numsSize, int target) { int i, j; int *indices=(int *)malloc(2*sizeof(int)); for (i = 0; i<numsSize; i++) for (j = i+1; j<numsSize; j++) if (nums[i] + nums[j] == target) { indices[0]=i; indices[1]=j; return indices; } return 0;}
令人吃惊的是这个算法的运行时间竟然打败了80%的提交算法，我自己都惊了。我猜那80%的人是遍历所有可能之后才返回indices。总之，不管如何，暴力(brute force)肯定不会是这题的最优解法。
暴力法的时间复杂度很明显是O(n^2)，那么更快的算法是什么呢。
如果我们采用桶排序的思想建立一个integer范围大小的数组bucket，扫描一遍输入数组，将bucket数组初始化，再扫描一遍输入数组，对每个输入元素检查bucket[target-nums[i]]的值，如果是1则往后扫描使得nums[j]==target-nums[i]，然后return[i,j]。这个算法是一个O(n)的算法。但是一个建立integer范围大小的数组空间消耗也太大了，粗略算了一下需要16G的内存空间，直接GG。
但是大体思路是正确的，如果我们能快速地确定target-nums[i]是否存在，就能省去许多无谓的扫描。但是通过一个integer范围大小的数组来创建一个直接映射表是不可行的，那么思路就比较明确了，哈希表呗。
typedef struct node{ int indice; int value; struct node *next;}node;node map[197];int hashFunc(int key){ if(key<0) key=-key; return key%97;}void insert(int i, int num) { node *tmp,*p; int val; val = hashFunc(num); tmp =(node *) malloc(sizeof(node)); tmp->indice = i; tmp->value =http://www.mamicode.com/ num; tmp->next = NULL; for (p = &map[val]; p->next != NULL; p = p->next) ; p->next = tmp;}int search(int num){ int val=hashFunc(num); node *p; for(p=map[val].next;p!=NULL;p=p->next) if(p->value=http://www.mamicode.com/=num) return p->indice; return -1;}int* twoSum(int* nums, int numsSize, int target) { int i, j; for(i=0;i<197;i++) map[i].next=NULL; int *indices=(int *)malloc(2*sizeof(int)); for (i = 0; i<numsSize; i++){ insert(i,nums[i]); j=search(target-nums[i]); if(j!=-1&&j!=i){ indices[0]=j; indices[1]=i; return indices; } } return 0;}
暴力法的时间是209ms，用哈希表的话这个时间就降到了9ms，适当加大map数组的大小，可以达到6ms左右。大概能击败92%的C提交。接下来似乎也没有什么好提速的地方了，比我快的应该是轮子比我造得圆造得好，我还是要多学习一个。
Two Sum问题