algorithm - 在多个排序数组中搜索及其复杂性

Question

给定3个排序数组。从每个数组中找出 3 个元素，满足 a+b=c。可以做到小于 O(n^3) 的时间复杂度吗？请帮我。

Answer 1

调用三个数组A,B和C, 和元素a,b和c。

在循环前两个数组时，由于ifa是固定的，b只能增加，c也只能增加。

因此，您不必C每次有一对aand时都要循环b；只是循环，C虽然循环B会做。

现在假设所有三个数组的长度都是 O(N)，时间复杂度是 O(N^2)，因为对于 中的每个值A，你需要遍历所有的B和所有的C，这个数字是 O(N)。

Answer 2

它可以在 O(N^2 * logN) 复杂度中完成，方法是遍历 2 个数组的 a 和 b 并在第三个数组中对 c 进行二进制搜索。

另一种方法是 O(N^2)，通过将其中一个数组的元素插入散列，在其他两个数组中迭代 a 和 b 并查看散列中是否存在 c = (a + b)。