arrays - 给定 4 个未排序的数组，用 sum 找到所有可能的四元组 给定四个长度相等的数组，它们没有排序，它们有唯一的元素，但是数组之间的元素可能会发生冲突，所以我们被要求从每个数组中选择一个元素并满足这个条件 "x1+x2+x3+x4 < m"并计算所有可能的解决方案。 我们可以做一些比排序所有数组并在 O(n^3*logn) 中做更好的事情吗？

Question

给定四个长度相等的数组，它们没有排序，它们有唯一的元素，但是数组之间的元素可能会发生冲突，所以我们被要求从每个数组中选择一个元素并满足这个条件 "x1+x2+x3+x4 < m"并计算所有可能的解决方案。

我们可以做一些比排序所有数组并在 O(n^3*logn) 中做更好的事情吗？

Answer 1

1. 生成一个数组，其中包含 x1 和 x2 中元素之间的所有总和。这将有 O(n^2) 个元素。让我们称之为 arr0
2. 对 x3 和 x4 执行相同的操作。让我们称之为 arr1
3. 对两者进行排序

4. 现在我们将问题简化为从 2 个排序数组中找到元素之间的总和 < m 的数量。

   p0 = 0
   p1 = arr1.length - 1
   qty = 0
   while(p0 != p1)
       while(p1 >= 0 and arr0[p0] + arr1[p1] >= m) p1--;
       if (p1 <= p0) break;
       qty += p1
       po++
   

这个小算法将解决 O(length(arr0) + length(arr1)) 中的问题，因为 p1 指针总是减小而 p0 总是增加，并且对于每个循环，我们总是增加或减少其中一个

总的来说，这给了我们一个 O(n^2) 来生成对，O(n^2 * log n^2) 来对它们进行排序，O(n^2) 来计算四元组。