确定 2 个数组是否不相交的算法

Question

使用确定的理想散列函数给出随机期望线性时间算法两个数组 A[1..n] 和 B[1..n] 是否不相交，即 A 的元素是否也是 B 的元素。

谁能告诉我如何做到这一点，甚至如何开始考虑它？

Answer 1

for element in a:
  hasha{element} = 1

for element in b:
  if hasha{element} == 1:
    print element "found in both"

时间:O(len(a)+len(b))