algorithm - 从 4 个不同序列的元素中找到总和 x

Question

这是我的问题:

给定一个数 x 和 4 个序列 A、B、C 和 D，每个 n 个数，判断是否存在一些数 a 来自 A，b 来自 B，c 来自 C，d 来自 D，使得 x = a+ b+c+d。允许的操作是比较、添加和交换。设计一个最坏情况运行时间小于 n^4 的高效算法来解决这个问题。

我不知道从哪里开始，希望得到一些帮助!

Answer 1

您可以执行以下操作:

1. 通过对 A 和 B 之间的每一对求和，对 C 和 D 求和来创建对和数组 AB=A+B，CD=C+D(AB 和 CD 都是 n^2 个元素的数组)- O(n^2)
2. 对数组 AB、CD 进行排序 - O(n^2 log(n))(此方法归功于 user58697。早些时候我提出了一种不同的方法，我认为它具有更好的复杂性, 但他 (s) 指出了我的错误。)
3. 分配索引 abi = (n^2-1), cdi = 0

4. 调查 AB[abi]+CD[cdi]，检查条件和递增/递减指标

   1. 计算总和=AB[abi]+CD[cdi]
   2. 如果总和等于 x:存在这样的组合! (停止算法)
   3. 如果 sum < x: 递增 cdi (++cdi)
   4. 如果 sum > x: 递减 abi (--abi)
   5. 如果 (abi < 0) 或 (cdi >= n^2):不存在这样的组合! (停止算法)
   6. 回到 4.1。

   每次执行第 4 步时，索引都会递增或递减(或者算法停止)，因此我们最多执行第 4 步 2*n^2 次(两个数组中的元素数)- O (n^2)

总而言之，我们有 O(n^2 log(n))