给定两个数组 a 和 b.找到所有元素对 (a1,b1)，使得 a1 属于数组 A，b1 属于数组 B，其和 a1+b1 = k [英] Given two arrays a and b .Find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k

问题描述

我正在寻找具有最小时间和空间复杂度的以下算法的解决方案.

I am looking for the solution of following algorithm with minimal time and space complexity.

给定两个数组 a 和 b，找出所有元素对 (a1,b1)，使得 a1 属于数组 A，b1 属于数组 B，其和 a1+b1 = k(任意整数).

Given two arrays a and b, find all pairs of elements (a1,b1) such that a1 belongs to Array A and b1 belongs to Array B whose sum a1+b1 = k (any integer).

我能够提出 O(n log n) 方法，我们将对数组中的一个进行排序，比如 A 并且对于数组 B 中的每个元素 b，在排序后的数组 A 上进行二进制搜索以获得值 (Kb).

I was able to come up with O(n log n) approach where we will sort one of the array say A and for each of the element b in array B, do binary search on sorted array A for value (K-b) .

我们可以进一步改进它吗?

Can we improve it any further?

推荐答案

如果你对最大可能数量有限制(我们将其命名为 M)，那么你可以在 O(M+n) 内得到解决方案.

If you have a limit on the maximum possible number (let's name it M) then you can have a solution in O(M+n).

布尔数组 false 并将 A 的元素的所有值标记为 true.然后对于 B 的每个元素 b 检查元素编号 K-b 是否标记为 true.

Boolean array of false and mark as true all value for element of A. Then for each element b of B check if the element number K-b is marked as true.

如果您使用哈希映射而不是大数组，则可以改进它.但我不会认为在这类问题中，hash-map 是一种作弊.

You can improve it if you are using an hash-map instead of a big array. But I would not consider that in this kind of questions hash-map is kind of cheating.

无论如何它会给你 O(n) 的插入，然后 O(n) 的查询，总共 O(n).

Anyway it would give you O(n) for insertion and then O(n) for query, O(n) in total.

这可能有用的一种情况.

One case where this might be useful.

• 您有大小为 10^6 的未排序向量，因此对它们进行排序和匹配的时间为 O(n log n)，n = 10^6.
• 你需要做这个操作 10^6 次(不同的向量)，复杂度为 O(n*n*log n).
• 最大值为 10^9.

使用我的想法不是布尔值而是整数(每次运行时递增)会给你一个复杂度:

Using my idea not with boolean but integer (incremented at each run) gives you a complexity of :

• "O(10^9)" 创建数组(同样的空间复杂度)
• 每次运行 O(n)，因此总计 O(n*n).

您正在使用更多空间，但在这种情况下您将速度提高了 log(n) ~=20 倍！

You are using more space but you've increased speed by a factor log(n) ~=20 in this case !

这篇关于给定两个数组 a 和 b.找到所有元素对 (a1,b1)，使得 a1 属于数组 A，b1 属于数组 B，其和 a1+b1 = k的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！