时间戳

首页 > 解决方案 > 找到具有特定总和的数字对

algorithm - 找到具有特定总和的数字对

问题描述

考虑 2 个正整数数组。我们得到了一些预定义的整数常量N。现在，我们必须找到对，其中 1 个元素来自 1 个数组，2 - 来自第二个数组，使得整数之和等于N。如果没有找到这样的对，则返回总和最接近（但不超过）N的对（如果它们的总和相等，则可以是几对）

我有唯一的解决方案：遍历所有可能的对，如果我们遇到一对更近的距离，清理结果数组并将其放在那里。如果我们遇到精确距离的对，则清除距离较小的对并将该对放入结果数组中。

我相信有更有效的方法来解决这个问题，你对此有什么想法吗？

标签： algorithm

解决方案

所以我们有数组A，B我们想找出

  a + b <= N   where a belongs to A and b belongs to B

这样

  (N - a - b) is minimum

我们可以做到以下

  1. 排序B数组：|B| * log('B')时间复杂度
  2. 借助二分搜索，在数组a中A找到最接近N - a值 ( b) 的每个：时间复杂度B|A| * log(|B|)
  3. 跟踪最佳（最少）a和b配对

总时间复杂度

|B| * log('B') + |A| * log(|B|) = (|A| + |B|) * log(|B|)

如果|B| > |A|我们可以对数组进行排序A和扫描B并且具有(|A| + |B|) * log(|A|)时间复杂度

如果|A| ~ |B| ~ M我们有M * log(M)时间复杂度

推荐阅读