arrays - 算法题: select one number from each of the five arrays, 检查它们的和是否可以是2018？

Question

问题:

有五个未排序的数字数组，从每个数组中仅选择一个数字。检查这五个数字的总和是否可以为2018。如果可以，则返回true。否则，返回 false。

我的解决方案:

最天真的一个...

sort the array in descending order
for a in arr1:
  for b in arr2:
     for c in arr3:
        for d in arr4:
           for e in arr5:
              if a+b+c+d+e == 2018:
                  return true
return false

我的解决方案的结果:

时间超过限制

---

这是我几周前在面试时遇到的一个问题。我不知道如何解决，所以写在这里寻求帮助。

Answer 1

简单的想法。创建前 3 个数组之和的排序列表 ABC。创建第二个 2 个数组之和的反向排序列表 DE。到目前为止，这需要空间 O(n^3) 和时间 O(n^3 log(n))。

现在开始将 ABC 中的元素与 DE 中的元素相加。每当总和低于 2018 年时，就按 ABC 前进。每次在 DE 中都会提前。如果您发现 2018 年，您的答案是正确。否则它是False。最终比较的时间复杂度为O(n^3 + n^2)。总体运行时间为O(n^3 log(n))。

如果您擅长使用优先级队列，您实际上可以使用不超过 O(n^2) 内存按排序顺序生成 ABC。但运行时间无法改善。