从 4 个不同序列的元素中找到总和 x
Find a sum x from elements from 4 differens sequences
这是我的问题：
给定一个数x和4个数列A、B、C、D，每n个数，判断是否存在一些数a来自A，b来自B，c来自C，d来自D使得x = a+b+c+d。允许的操作是比较、添加和交换。设计一个有效的算法来解决这个问题，最坏情况 运行 时间少于 n^4.
我不知道从哪里开始，希望得到一些帮助！
您可以执行以下操作：
- 通过对 A 和 B 之间的每一对求和，对 C 和 D 求和来创建对和数组 AB=A+B，CD=C+D（AB 和 CD 都是 n^2 个元素的数组）- O(n^2)
- 对数组 AB、CD 进行排序 - O(n^2 log(n))（此方法归功于 user58697。之前我曾建议过一种不同的方法我认为会有更好的复杂性，但他指出了我的错误。）
- 分配索引 abi = (n^2-1), cdi = 0
调查 AB[abi]+CD[cdi]，检查条件和 increment/decrement 指数
- 计算总和=AB[abi]+CD[cdi]
- 如果总和等于 x：存在这样的组合！ (停止算法)
- 如果总和 < x：增加 cdi (++cdi)
- 如果 sum > x: 递减 abi (--abi)
- 如果 (abi < 0) 或 (cdi >= n^2)：不存在这样的组合！ (停止算法)
- 返回 4.1。
每次执行第 4 步时，索引都会递增或递减（或者算法停止），因此我们最多执行第 4 步 2*n^2 次（两个数组中的元素数）- O(n^2)
总而言之，我们有 O(n^2 log(n))
这是我的问题：
给定一个数x和4个数列A、B、C、D，每n个数，判断是否存在一些数a来自A，b来自B，c来自C，d来自D使得x = a+b+c+d。允许的操作是比较、添加和交换。设计一个有效的算法来解决这个问题，最坏情况 运行 时间少于 n^4.
我不知道从哪里开始，希望得到一些帮助！
您可以执行以下操作：
- 通过对 A 和 B 之间的每一对求和，对 C 和 D 求和来创建对和数组 AB=A+B，CD=C+D（AB 和 CD 都是 n^2 个元素的数组）- O(n^2)
- 对数组 AB、CD 进行排序 - O(n^2 log(n))（此方法归功于 user58697。之前我曾建议过一种不同的方法我认为会有更好的复杂性，但他指出了我的错误。）
- 分配索引 abi = (n^2-1), cdi = 0
调查 AB[abi]+CD[cdi]，检查条件和 increment/decrement 指数
- 计算总和=AB[abi]+CD[cdi]
- 如果总和等于 x：存在这样的组合！ (停止算法)
- 如果总和 < x：增加 cdi (++cdi)
- 如果 sum > x: 递减 abi (--abi)
- 如果 (abi < 0) 或 (cdi >= n^2)：不存在这样的组合！ (停止算法)
- 返回 4.1。
每次执行第 4 步时，索引都会递增或递减（或者算法停止），因此我们最多执行第 4 步 2*n^2 次（两个数组中的元素数）- O(n^2)
总而言之，我们有 O(n^2 log(n))