转载

leetcode速度才是王道 1.Two Sum

1. Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

题目的意思是给你一个目标数（target），让你从给定的数组中找出两个数nums[x]和nums[y]相加等于target，并返回这两个值的索引x+1和y+1（需要加1是因为题目要求索引不是以0开始的）。

这个题目的一个难点是target可以是0也可以是负数，这一点题目里没说清楚，在测试用例里面会出现。因为追求速度，所以所有leetcode的代码我都会用C写。

因为第一次刷leetcode，没啥经验的我一上来就too young too simple的来了个全暴力的搜索法，先固定第一个数，然后从固定的数往后面搜索第二个数，这个原始的暴力破解法时间复杂度接近n ²

 1 int* twoSum(int* nums, int numsSize, int target) {  2     int *indices = (int*)malloc(2 * sizeof (int));  3     for(int i=0; i<numsSize-1; i++)  4     {  5         for(int j=i+1; j<numsSize; j++)  6         {  7             if(nums[i] + nums[j] == target)  8             {  9                 indices[0] = i; 10                 indices[1] = j; 11                 return indices; 12             } 13         } 14     } 15     return NULL; 16 }

Time Limit Exceeded 被leetcode无情的拒绝了

于是我开始了新的尝试，最开始想到的是调整外存循环的步长，也就是每次固定两个数据，第二个数据分别和固定的两个数据相加然后和target进行比较，这样做的目的主要是为了减少内存访问的次数，以为第二个数据取一次可以使用两次，时间复杂度依旧接近n ² ，应该是因为内存遍历次数减少，所以有幸通过。代码如下：

 1 int* twoSum(int* nums, int numsSize, int target) {  2     int *indices = (int*)malloc(2 * sizeof (int));  3     for(int i=0; i<numsSize-1; i+=2)  4     {  5         if(nums[i] + nums[i+1] == target)  6         {  7             indices[0] = i + 1;  8             indices[1] = i + 2;  9             return indices; 10         } 11         else 12         { 13             for(int j=i+2; j<numsSize; j++) 14             { 15                 if(nums[i] + nums[j] == target) 16                 { 17                     indices[0] = i + 1; 18                     indices[1] = j + 1; 19                     return indices; 20                 } 21                 else if(nums[i + 1] + nums[j] == target) 22                 { 23                     indices[0] = i + 2; 24                     indices[1] = j + 1; 25                     return indices; 26                 } 27             } 28         }    29     } 30     return NULL; 31 }

Runtime: 224 ms

这次很荣幸的通过了，不过速度实在是太慢，我尝试过将外层循环的步长改为4，速度有提升，但是没有太想大效果，最好的速度是194ms。

看到最好的4ms的速度，我依然不想就此罢手，于是我想到了hash，在使用hash的时候，内存的用法有很多比较不错的改进，都会记录在此。

  1 #define LIST_LENGTH 100   2    3 typedef struct Item Item;   4    5 struct Item   6 {   7     int value;   8     int index;   9     Item * next;  10 };  11   12 typedef struct List  13 {  14     Item *head;  15     Item *end;  16 } List;  17   18 void insertItem(List *list, Item *item)  19 {  20     int key = ( item->value / 2 ) % LIST_LENGTH;  21       22     if ( !list[key].head )  23     {  24         list[key].head = item;  25         list[key].end = item;  26     }  27     else  28     {  29         list[key].end->next = item;  30         list[key].end = item;  31     }  32       33 }  34   35 int searchValue(List *list, int value)  36 {  37     int key = (value / 2) % LIST_LENGTH;  38       39     Item *p = list[key].head;  40       41     while(p)  42     {  43         if(value == p->value)  44         {  45             return p->index + 1;  46         }  47         p = p->next;      48     }  49     return 0;  50 }  51   52 void listFree(List *list)  53 {  54     for(int i=0; i<LIST_LENGTH; i++)  55     {  56           57         Item *p, *q;  58         p = list[i].head;  59           60         while(p)  61         {  62             q = p->next;  63             free(p);  64             p = q;      65         }  66           67     }  68       69     free(list);  70 }  71   72 int* twoSum(int* nums, int numsSize, int target) {  73     if(numsSize < 100)  74     {  75         return twoSumShort(nums, numsSize, target);  76     }  77     int *res = (int*)malloc(2 * sizeof(int));  78     List *list = (List*)malloc(sizeof(List) * LIST_LENGTH);  79     memset(list, 0, sizeof(List*) * LIST_LENGTH);  80     for(int i=0; i<numsSize; i++)  81     {  82         Item *item = (Item*)malloc(sizeof(Item));  83         item->value = nums[i];  84         item->index = i;  85         item->next = NULL;  86         insertItem(list, item);  87     }  88       89     for(int i=0; i<target; i++)  90     {  91         int x = searchValue(list, i);  92         int y = searchValue(list, target - i);  93   94         if(x && y)  95         {  96             res[0] = x < y ? x : y;  97             res[1] = x + y - res[0];  98             break;  99         } 100     } 101     listFree(list); 102     return res; 103 }

这个是使用hash的雏形，当然这份代码里面存在很多问题，一下会一一解释

问题1：为了减少搜索的次数，代码line89~100尝试将target分为[0, target], [1, target-1]...这些可能性，然后分别使用hash搜索前后连个值，但是这里漏掉的数组中有负数的可能性，比如说target = 0 = -10000 + 10000，所以不能以target作为搜索的支点。

问题2：在构建hash表的过程中，line80~87重复了numsSize次调用malloc为节点分配内存，因为malloc是很耗时的一个函数，所以这会导致函数运行起来非常慢。

问题3：因为动态分配内存了，所以引入了释放内存的操作ListFree函数，这个是可以想办法避免的

对照以上问题，经过多次尝试后，终于出了一个最快版的，代码如下：

 1 #define LIST_LENGTH 1000  2   3 typedef struct Item Item;  4   5 struct Item  6 {  7     int value;  8     int index;  9     Item * next; 10 }; 11  12 typedef struct List 13 { 14     Item *head; 15     Item *end; 16 } List; 17  18 void insertItem(List *list, Item *item) 19 { 20     int key = (unsigned int)( item->value) % LIST_LENGTH; 21     if ( !list[key].head ) 22     { 23         list[key].head = item; 24         list[key].end = item; 25     } 26     else 27     { 28         list[key].end->next = item; 29         list[key].end = item; 30     } 31      32 } 33  34 int searchValue(List *list, int value) 35 { 36     int key = (unsigned int)(value) % LIST_LENGTH; 37     Item *p = list[key].head; 38      39     while(p) 40     { 41         if(value == p->value) 42         { 43             return p->index + 1; 44         } 45         p = p->next;     46     } 47     return 0; 48 } 49  50 // use hash 51 int* twoSum(int* nums, int numsSize, int target) { 52     int *res = (int*)malloc(2 * sizeof(int)); 53     List list[LIST_LENGTH]; 54     memset(list, 0, sizeof(List) * LIST_LENGTH); 55     Item item[numsSize]; 56     memset(item, 0, sizeof(Item) * numsSize); 57  58     for(int i=0; i<numsSize; i++) 59     {     60         item[i].value = nums[i]; 61         item[i].index = i; 62         insertItem(list, &item[i]); 63     } 64      65     for(int i=0; i<numsSize; i++) 66     { 67         int x = i + 1; 68         int y = searchValue(list, target - nums[i]); 69  70         if(x && y && (x ^ y)) 71         { 72             res[0] = x < y ? x : y; 73             res[1] = x + y - res[0]; 74             break; 75         } 76     } 77      78     return res; 79 }

Runtime: 4 ms

看这这个4ms，真是激动不已啊，终于站到最前面了，这份代码对前面三个问题都进行处理。

问题1解决方法：

第一个数据通过nums数组来固定，通过hash来查找第二个相配的的数据 searchValue(list, target - nums[i]);如果不出现hash冲突，那麽此算法的时间复杂度为N，很好的解决了第一个问题

问题2解决办法：对于通过for循环重复为数组中每个节点分配内存的做法可以通过一次性给所有节点分配好内存来改进 Item *item = (Item*)malloc(sizeof(Item) * numsSize); ，这样先将所有的内存分配好，构建hash表的时候，直接通过给指针赋值，让其指向对应的内存就行，这样也方便也释放内存。

问题3解决办法：因为依旧使用了malloc分配堆内存，需要手动释放，所有问题2的解决办法依旧不是最好。因为只需要返回两个index，所有最后选择了使用栈内存（代码line53~56），这样速度够快，也不需要手动释放内存，因此，一个4ms的算法就此诞生啦！

正文到此结束