一个"2-SUM"问题

题目要求：

Download the text file here. (Right click and save link as).

The goal of this problem is to implement a variant of the 2-SUM algorithm (covered in the Week 6 lecture on hash table applications).

The file contains 1 million integers, both positive and negative (there might be some repetitions!).This is your array of integers, with the ith row of the file specifying the ith entry of the array.

Your task is to compute the number of target values t in the interval [-10000,10000] (inclusive) such that there are distinct numbers x,y in the input file that satisfy x+y=t. (NOTE: ensuring distinctness requires a one-line addition to the algorithm from lecture.)

Write your numeric answer (an integer between 0 and 20001) in the space provided.

OPTIONAL CHALLENGE: If this problem is too easy for you, try implementing your own hash table for it. For example, you could compare performance under the chaining and open addressing approaches to resolving collisions.

大致意思是说，有一百万个数字（正负都有，且可能重复）。目标是要寻找到两个数x和y，使得x+y属于[-10000, 10000]的范围中，且x和y在所有数当中都是唯一存在的，最后输出所有可能的和的个数。

文件中的数据差不多是这样子的：

...

-92205919974

-65150999169

-96247986144

70191728682

-59670982771

-10202710755

-72167080349

-19221613985

80341418823

-79433686277

87351713416

6084932343

40801752610

44028247959

84203784346

-28120386474

59064431376

39436465566

-89458683408

-64200776240

-42582579303

-62656888535

55650079602

62954175548

33713639217

70259349593

-97472959477

41890148139

44216212976

26864335558

...

解题思路：

起初采用了最暴力的方法，直接把这些数字塞进一个hash table中，然后遍历着去查询（这个方法很不好，所以就不详述了），结果运行了很久都没有跑出结果，遂直接放弃这种方法。

这里的问题在于如下两点：

数据量多达一百万条；
大部分数对相加的和，远超要求的范围之外。

因此针对问题的实际情况进行了些许优化，大致思路如下：

假设X为文件中的一个数字；
创建一个hash table，它的键为X/10000，值为由对应X组成的set。这样就相当于把输入的数据以10000作为一个范围对其进行划分，最后划分成若干组数据，之所以要将10000作为划分的范围，是因为题目中要求数对的和在[-10000, 10000]的范围中，这样对于我们这里的hash table，给定一个key1，我们就能知道可能有哪些key2对应集合中的数与key1集合中的数相加，是可以在要求的范围中的；
具体而言，对于一个key1，可取的key2有：{-key1-2, -key1-1, -key1}这三个。注意因为之前的X/10000是整除，其结果为向下取整，如 -14000 / 10000 = -2；
在已知了key1与key2之后，对其集合中的数进行循环遍历，如果相加的和在题目要求的范围内，那么就将计数器加一。

利用上述思路，可以避免大量的不必要的运算，另外我们还可以对其进行进一步的优化：

对key1进行遍历的时候，只取key1小于或等于零的值，这样可以进一步减少重复计算；
创建一个保存结果的set，如果找到了满足要求的数对(x, y)，那么就置result[x+y] = True，最后输出result的大小。

代码实现：

有了上述的思路，利用Python对其进行了实现，代码如下：

result = {}

dic = {}

input_file = open("algo1-programming_prob-2sum.txt")

# 读入数据

for line in input_file:

    num = long(line)

    key = num/10000

    if key not in dic:

        dic[key] = {}

    # 这里记录数据出现的次数，用来判断该数是否是唯一的

    if num in dic[key]:

        dic[key][num] += 1

    else:

        dic[key][num] = 1

for key1 in dic:

    # 忽略key1 > 0的情况，减少不必要的重复计算

    if key1 > 0:

        continue

    # 根据给定的key1，可以推测出key2可取的值

    for key2 in range(-key1-2, -key1 + 1):

        if key2 in dic:

            # 对key1和key2对应集合中的数进行遍历

            for value2 in dic[key2]:

                for value1 in dic[key1]:

                    # 判断这两个数是否是唯一的

                    if dic[key1][value1] != 1 or dic[key2][value2] != 1:

                        continue

                    sum_tmp = value1+value2

                    # 判断两数之和是否在题目要求的范围内

                    if abs(sum_tmp) <= 10000 and sum_tmp not in result:

                        result[sum] = True

# 输出结果

print len(result)

input_file.close()

这段代码在我的电脑上运行仅需要大约3-4秒的时间就能跑出结果（包含读取数据的I/O操作的时间），可见该方法有效地避免了大量不必要的计算。

另外，题目中要求找到唯一存在的数对(x, y)，但是如果把代码中判断唯一性的那个条件判断去除，得到的结果也是一样的，这也许和给出的数据有关。

秒客网

一个"2-SUM"问题

相关文章