本文共 1772 字，大约阅读时间需要 5 分钟。

注：leetcode的要求是第一列中相同的数只算一次。POJ是单独算的。

比如

4

0 0 0 0 

0 0 0 0

0 0 0 0

0 0 0 0

这组测试数据，leetcode上面要求返回1，而在POJ上要求返回4*4*4*4 = 256。

好吧。上次写POJ解题报告的解题的时间为“2011-03-18 01:41”。现在时间是“2012-10-20 15:48”。我就不继续说下去了。免得自己太难过。。。

这次写POJ这道题的缘由是在准备笔试面试，在leetcode上见到一道题是是求所以a+b+c+d=0的可能的组数。于是看到了POJ这道题的链接。

当时在leetcode的OJ通过的做法是先排序，然后对两行遍历，另外两行一个指针从上往下走，一个指针从下往上走。时间复杂度是O(n^3)。

但在POJ，这是无法通过的。。。

于是，在尝试把前两组遍历，求出所有可能的和，保存在map中，然后遍历后两组，对每一个和sum，在map中找-sum。这样的时间复杂度是O(n^2*log*(n^2))。

但在POJ，这是无法通过的。。。

于是，开始“参考”网上的做法，使用hash。后来提交的时候还是各种RE，后来我的程序改得和网上的一模一样了。同学们可以直接移步到这里：

因为程序一模一样了，我也就不贴程序了。

这道题给我长进是：链式Hash

下面的hash函数使用两个大素数取余，

int hash(int num){

        return (num+3899971)%3999971; }

为什么用这种方法可以见

但是估计看完也只有直观的感受，那就是用素数会让整个hash表尽可能都用到。当然，用这是由于“数学原理”来理解也就差不多了。。。

int tot;

struct edge{         int v, next, cnt; }edge[3999971]; int head[3999971];

这是链式hash表实现的数据结构，实际上没有使用链表，而是使用数组，用数组索引代替指针（原因是在POJ中一次开很大的数组是允许的，这样可以避免每次动态申请空间的时间开销，算是用空间换时间）。head用做索引，指向hash值为s的第一个num。这个num及所有hash值为s的数保存在edge数组中。edge中的每一个元素是一个结构体，保存这个元素的num（用v表示），下一跳在edge数组中的索引，还有num出现了多少次（用cnt表示）。hash值取0~3999970（见hash函数中的取余素数）。所以两个数组开3999971这么大。

这也能看出取hash值的作用：用一个相对较小的空间保存所有可能出现的和，避免一个特大的空间（3999971 vs 2^30，因为每个数的范围为(+-)2^28）。

void add_edge(int num){

        int s=hash(num);         for(int i = head[s]; i != -1; i = edge[i].next){         if(edge[i].v == num){                 edge[i].cnt++;                 return ;         } }         edge[tot].v = num;         edge[tot].cnt = 1;         edge[tot].next = head[s];         head[s]=tot++; }

这是插入hash表的过程。首先对num取hash，根据head找到第一个hash值为s的数在edge中的索引，如果找到，则cnt加1。否则在edge表的末尾（索引为tot，tail of table）保存下这个数的信息（数值num， 计数为1）。注意的是这里让这个新的节点下一跳指向当前的头结点，然后更新头结点为这个新节点。这样实际上将节点插入在了这一系列值的最前列。体会下当head[s]为-1时，即没有值时的情况。这样写要比将新节点报错在链式表的末端要统一。

int find(int num){ int s=hash(num); for(int i=head[s];i!=-1;i=edge[i].next){ if(edge[i].v == num){ return edge[i].cnt; } } return 0; }

明白了插入的过程后查找的过程就顺其自然了。如果这条链上都没找到，则该数不存在。

转载地址：http://uxxli.baihongyu.com/