arrays - 给定 3 个排序数组 A、B、C 和数字 S，找到 i、j、k 使得 A[i] + B[j] + C[k] = S

Question

我刚刚发现如何在 O(n^2 log n) 时间内解决这个问题(假设每个数组的长度相同):

for each A[i]:
  for each B[j]:
    if A[i] + B[j] + C.binarySearch(S - A[i] - B[j]) == S:
       return (i, j, k)

有什么方法可以在O(n^2)时间内解决这个问题或者改进上面的算法吗？

Answer 1

你的算法还不错。相对于 n^2 , log(n)增长如此缓慢以至于它实际上可以被认为是一个常数。例如，对于 n = 1000000 , n^2 = 1000000000000和 log(n) = 20 .一次n变得足够大 log(n)有任何重大影响，n^2已经太大了，结果无论如何都无法计算。

受@YvesDaoust 启发的解决方案，但我不确定它是否完全相同:

• 对于每个 A[i] , 计算余数 R = S - A[i]这应该是一些 B[j] 的组合和 C[k] ;
• 让j = 0和 k = |C|-1 (C 中的最后一个索引)；
• 如果B[j] + C[k] < R , 增加 j ;
• 如果B[j] + C[k] > R , 减少 k ;
• 重复前两个步骤，直到 B[j] + C[k] = R或 j >= |B|或 k < 0

我建议不要通过微优化使算法过于复杂。对于任何相当小的数字集，它都足够快。如果数组对于这种方法来说变得太大，您的问题将成为机器学习方法(例如爬山法)的一个很好的候选者。