java - 如何在线性时间内找到 2-sum？

Question

我参加了 Algorithms, Part II Coursera 上的类(class)，其中一个面试题(未评分)如下:

2-sum. Given an array a of n 64-bit integers and a target value T, determine whether there are two distinct integers i and j such that a[i] + a[j] = T. Your algorithm should run in linear time in the worst case.

Hint: sort the array in linear time.

我可以想出几种解决方法:

1. 一次性将元素插入到哈希表中。然后进行第二遍，寻找T - a[i]在哈希表中。哈希表的空间复杂度为 O(n)，2 次传递的空间复杂度为 O(n)。此解决方案满足问题中规定的时间要求。

2. 排序数组，然后运行2个指针i和 j从开头和结尾分别寻找a[i] + a[j] = T .如果a[i] + a[j] < T , 递增 i , 否则递减 j .空间复杂度取决于排序算法；假设快速排序不需要额外的空间。时间复杂度nlogn，所以没有达到题中的时间要求。

3. 考虑到问题是在基数排序讲座之后给出的，我假设意图是使用基数排序之一。由于问题指定 64 位整数，因此使用 long 的二进制表示，并使用 In-place MSD radix sort ，数组可以在线性时间内就地排序。这似乎是最好的方法。

其他想法？

附言我看过这个question ，但它假定一个排序数组，并且那里的所有答案都使用某种哈希。

我也看过这个question但对于 2-sum 的特定情况，它似乎过于复杂。

Answer 1

我分析了您的观察结果，并认为符合要求的是:

Insert the elements in a hash table in one pass. Then make a 2nd pass, looking for T - a[i] in the hash table. Space complexity is O(n) for the hash table, and O(n) for the 2 passes. This solution meets the time requirement stated in the question.

我认为这种方法不符合要求，因为理论上 hashtable 最坏情况插入复杂度为 O(n)。

正如你所说，你研究了基数排序，我相信这是要走的路，你可以在时间要求内对数组进行排序，然后你可以使用双指针技术来检查是否有是总和 T:

int left = 0, right = array_size - 1;
boolean found = false;
while (left < right) {

    if (a[left] + a[right] == T) {              
        found = true;
    }
    else if (a[left] + a[right] < T) {
        left++;
    }
    else {
        right--;
    }
}