给定 4 个未排序的数组，找到所有可能的四倍，总和为 <m

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(长度(arr0( + length(arr1((中的问题，因为 p1 指针总是减少，p0 总是增加，对于每个循环，我们总是增加或减少其中一个

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