哈希相关问题

计数排序(Count Sort)

计数排序是最简单的基于哈希表的排序算法，常用的排序算法是比较排序，但基于哈希表的排序一般都属于非比较排序。这类排序算法的特点是牺牲空间来换取更低的时间复杂度，这个时间复杂度甚至低于比较排序的理论极限\(O(n\lg n)\)。但这类排序对输入的数有限制、并且可能会占用相当多的空间，所以应用并不如比较排序广。

计数排序要求输入的每个数都必须是整数，算法流程是先创建空哈希表，然后遍历输入找到最大值\(max\)和最小值\(min\)，再在哈希表中依次插入关键字\(min, min+1,…,max\)并让每个关键字关联一个值用来表示“关键字在输入中的个数”，所以值初始都为0。然后遍历输入并在哈希表统计各数的出现次数，最后根据\(max\)和\(min\)按\(min, min+1,…,max\)次序找到关键字对应的值\(n\)然后打印\(n\)次关键字，整个过程打印的内容和次序就是输入的升序排序。

设\(k = max – min + 1\)表示输入范围的大小，\(n\)表示输入元素数，算法的时间复杂度和空间复杂度都是\(O(n+k)\)，说明算法适用于\(k\)不显著大于\(n\)的情况。下面是算法的Python实现，这里直接用Python的dict数据类型作为哈希表。

两数之和(2-Sum Problem)

该问题是“给定数组\(nums\)和值\(x\)，求出任意一对\(a,b(a<b)\)使\(nums[a]+nums[b]=x\)，并按数组形式返回\([a,b]\)，\(nums\)保证有符合该要求的解。要求时间复杂度和额外空间都是\(O(n)\)”。容易想到通过2层循环来寻找解，这样不需要额外空间，但时间复杂度是\(O(n^2)\)。该问题利用哈希表来解决能达到其最优的时间复杂度，具体的步骤如下：

1) 初始化空哈希表\(d\)；

2) 从小到大枚举\(nums\)索引\(i\)，记录\(d[x – nums[i]] = i\)；

3) 从小到大枚举\(nums\)索引\(i\)，若关键字\(nums[i]\)在\(d\)中且\(i < d[nums[i]]\)，返回结果\([i, d[nums[i]]]\)；

步骤(2)结束时\(d[A]\)表示“与\(A\)的和为\(x\)的数中，索引最大的数的索引”。据题设\(nums\)有至少1对元素的和是\(x\)，那步骤(3)从小到大枚举索引\(i\)的过程中，一定能找到1个\(i\)，其等于某个这种元素对中，索引值小的元素的索引。下面是程序实现。

两数之和的总数

该问题是“给定数组\(nums\)和值\(x\)，求出满足两数之和等于\(x\)的元素对的总数目。要求时间复杂度和额外空间都是\(O(n)\)”。因为无需求具体索引，这里换个思路，先遍历\(nums\)构造哈希表\(d[A]\)表示“与\(A\)的和为\(x\)的数的总个数”。再次遍历\(nums\)的元素\(n\)，当发现\(n\)作为关键字在\(d\)中，若\(x-n\neq n\)则将计数增加\(d[n]\)，若\(x-n=n\)则将计数增加\(d[n] – 1\)。最终得到的计数是排列的计数而不是组合的计数，所以需要把计数除以2再作为结果返回。具体程序如下。

子数组之和

该问题是“给定数组\(nums\)和值\(x\)，求出任意一对\(a,b(a\leq b)\)使\(nums\)中索引为\(a,b\)的元素间的所有元素(包括端点)的和等于\(x\)，并按数组形式返回\([a,b]\)，\(nums\)保证有符合该要求的解。要求时间复杂度和额外空间都是\(O(n)\)”。解决方法是先整理\(nums\)的前缀和数组\(ps\)，问题转化为“找\(ps\)上的任意元素对，两者的差等于\(x\)”或“找\(ps\)上的单个元素，其值等于\(x\)”，把得到的索引或索引对处理下就能作为解。这里的“两数之差”问题和前面的“两数之和”问题类似，可以用哈希表\(O(n)\)代价的解决，“两数之差”相比“两数之和”理论上应该难一点点，因为被减数和减数是不能交换的。整个程序的步骤如下：

1) 求出\(nums\)的前缀和数组\(ps\)；

2) 从小到大枚举\(ps\)索引\(i\)，若\(ps[i] = 0\)则直接返回结果\([0,i]\)；

3) 初始化空哈希表\(d\)；

4) 从大到小枚举\(ps\)索引\(i\)，记录\(d[x + ps[i]] = i\)；

5) 从大到小枚举\(ps\)索引\(i\)，若关键字\(ps[i]\)在\(d\)中且\(d[ps[i]] < i\)，返回解\([d[ps[i]]+1, i]\)；

步骤(2)若没返回，说明\(a\)不可能是0，那\(x\)必然可作为2个\(ps\)不同元素的差。程序走到步骤(4)结束时，此时\(d[A]\)表示“等于\(A – x\)的数中，\(ps\)索引最小的数的索引”。此时根据题设存在至少一对\(m>n\)使\(ps[m] – ps[n] = x\)，所以步骤(5)从大到小枚举索引\(i\)的过程中，一定能找到这样的1个\(i\)，其等于符合要求的某对索引中，被减数的索引。此时减数的索引就是\(d[ps[i]]\)，还原到\(nums\)数组中就是\(nums[d[ps[i]]+1,…,i]\)的这些元素，所以就找到了一个解\([d[ps[i]]+1,i]\)。注意这里必须要限定\(m>n\)，即被减数索引大于减数，否则导致得到的差是\(-x\)而不是\(x\)。下面是程序实现。

回旋镖的总数

该问题是“给定数组\(p\)，其元素是\([x,y]\)表示平面的点，\(p\)中无重复的点。对于任意3个点，若线段\([p[i], p[j]]\)和\([p[i], p[k]]\)长度相等，序列\([p[i], p[j],p[k]]\)就构成1个回旋镖。问序列\(p\)能构成多少个回旋镖，注意3个点次序不完全相同也算不同的回旋镖”。该问题很容易用\(O(n^3)\)代价的3重循环解决，这里用1组哈希表实现\(O(n^2)\)代价的解法。具体就是为\(p\)每个点\(p[x]\)都建立1个哈希表\(T_x[d] = n>0\)表示“到\(p[x]\)的距离平方等于\(d\)的点的数目”，从中选2个做排列，排列数就是\(n(n-1)\)，这个排列数就表示“以\(p[x]\)为首个点，到\(p[x]\)的距离平方等于\(d\)的点”能构成的回旋镖总数。那么对所有哈希表和所有\(d\)求和就是总回旋镖数目，这里面不会有重合的情况，无论是\(d\)不同还是首个点不同都意味着不同的回旋镖。具体程序如下。

直线上最多的点

该问题是“给定数组，其元素是表示平面点的\([x,y]\)，其中\(x,y\)是整数且无重复的点。问最多有多少个点共线”。一种思路是建立2维哈希表\(d_1[i] = d_2, d_2[k] = n\)，其中\(i\)为点的索引，\(k\)是其他点与该点的\(\frac{\Delta y}{\Delta x}\)(斜率)，\(n\)是与该点的\(\frac{\Delta y}{\Delta x}\)等于\(k\)的所有其他点的数目。所以该2维哈希表中最大的\(n+1\)就是解，这里加1是因为索引为\(i\)的点本身还没有计数。这里有2个细节要注意：

1) 要特别处理\(\frac{\Delta y}{\Delta x} = \infty\)的情况。考虑到\(d_2\)是哈希表，所以可以直接加入固定的字符串关键字“inf”，这样\(d_2[inf]\)就统一表示使得\(\frac{\Delta y}{\Delta x} = \infty\)的所有其他点的总数；

2) 要避免计算\(\frac{\Delta y}{\Delta x} \)导致的浮点数精度问题，这里干脆换个思路不用除法来计算这个值。根据有理数定义，1个有理数可写成整数比\(\frac{A}{B}\)，如果还要求\(A,B\)互质，有理数可写成的整数对\((A,B)\)是唯一得。由于点坐标是整数，所以\(\frac{\Delta y}{\Delta x} \)都是有理数，约分后得到\(\frac{\Delta y’}{\Delta x’} = \frac{\Delta y}{\Delta x}\)，\(\Delta y’\)与\(\Delta x’\)互质。如果把\(\Delta y’\)与\(\Delta x’\)写成字符串“\(符号, |\Delta y’|, |\Delta x’|\)”。那么对于任何两个相等的\(\frac{\Delta y}{\Delta x}\)，经过上述约分和映射到字符串的操作，得到的字符串相等，干脆就用它来作为\(\frac{\Delta y}{\Delta x}\)的“值”，即\(d_2\)的关键字；

经上面2点考虑，\(d_2\)的关键字全都是字符串。下面是程序实现，其通过公约数实现“约分”。由于程序使用了2层循环，其中存在求公约数、得到字符串形式的\(d_2\)关键字的过程，如果假设它们是\(O(1)\)的，那么总代价是\(O(n^2)\)。