查找数组中总和为指定值的所有整数对

Question

设计一种算法来查找数组中总和为指定值的所有整数对.

我已经尝试使用哈希表来存储数组元素总和的条目,但它不是一个有效的解决方案.

我可以使用什么算法来有效地解决这个问题？

Answer 1

我不明白为什么哈希表方法是低效的,至少在算法分析术语中 - 在内存位置术语中无可否认,它可能非常糟糕.无论如何,扫描阵列两次......

第一次扫描 - 将所有数组元素放在哈希表中 - 总共O(n).单个插入只是摊销O(1),但关于摊销分析如何工作的一个巧妙的事情意味着O(n)是绝对的 - 不摊销.

第二次扫描 - 检查哈希表中的(sum - current) - 总计O(n).

这至少在理论上击败了O(n log n)排序和搜索方法.

然后,请注意您可以将两个扫描合并为一个.在第一次扫描期间遇到第二对时,您可以发现一对.在伪代码......

for i in array.range
  hashset.insert (array [i])

  diff = sum - array [i]
  if hashset.includes (diff)
    output diff, array [i]

如果您需要项目的位置,请使用散列图并在其中存储项目位置.如果需要处理重复项,则可能需要在哈希映射中存储计数.对于位置和重复,您可能需要一个起始指针的散列图,用于链接的位置列表.

这假设了哈希表的实现,但是在大多数当前语言和库中通常的实现给出了相当安全的假设.

BTW - 结合扫描不应被视为优化.迭代开销应该是微不足道的.对于非常大的数组,内存局部性问题可能会使单个传递稍微提高效率,但实际的内存局部性问题无论如何都会在哈希表查找中.

IMO是组合扫描的唯一真正原因是因为您只希望每对报告一次 - 在双扫描方法中处理它会更麻烦.

Answer 2

1. 如果数组已排序:

   设i = 0,j =数组的结尾,sum =您要查找的值,然后执行:

   如果i + j = sum,则输出(i,j).
   如果i + j <sum,则将i移动到右边的一个位置.
   如果i + j> sum,则将j移动到左侧的一个位置.

   时间复杂度:O(n).空间复杂度:O(1).

2. 如果数组未排序,有几种方法可以解决此问题:

   1. 对数组进行排序,然后使用上述方法.

   2. HashMap的:

      将所有元素存储在HashMap中.

      a+b=sum所以b=sum-a.对于a数组的每个元素,b从HashMap中查找.

      HashMap查找采用摊销的O(1).

      时间复杂度:O(n).空间复杂度:O(n).

   3. 位图:

      迭代输入以创建位图,其中每个位对应于元素值.假设输入是{2,5,8},然后我们将位图数组的索引2,5和8从二进制0切换到1.这需要每个元素O(1),因此总共为O(n).

      再次浏览输入.我们知道b=sum-a,因此对于a输入中的每个元素,都要查找它b,这可以完成,O(1)因为它是位图索引.这也总共需要O(n).

      时间复杂度:O(n)+ O(n)= O(n).空间复杂度:位图空间= O(n).

Answer 3

您甚至不需要将所有元素存储在hashmap中,然后进行扫描.您可以在第一次迭代期间进行扫描.

void foo(int[] A, int sum) {
    HashSet<Integer> set = new HashSet<Integer>();
    for (int e : A) {
        if (set.contains(sum-e)) {
            System.out.println(e + "," + (sum-e));
            // deal with the duplicated case
            set.remove(sum-e);
        } else {
            set.add(e);
        }
    }
}

Answer 4

如何排序数组,然后从两端进入？

Answer 5

假设所需的sum = R.

1. 对数组进行排序
2. 对于数组A(n)中的每个数,进行二分搜索以找到数A(x),使得A(n)+ A(x)= R