有效地计算给定总和的所有对

Question

我遇到了以下问题。

给定一个列表，其中每个项目表示以秒为单位表示的歌曲持续时间，返回歌曲对的总数，例如它们的持续时间总和为分钟（例如，1m0s、2m0s、..）

示例：
输入：[10,50,20,110,40]
输出：3（考虑索引 (0,1),(0,3),(2,4) 处的对）

我只能想到一种蛮力的方法，我会考虑所有对的歌曲。这种方法的时间复杂度是 O(n^2)。
有没有更好的方法来做到这一点？

Answer 1

给定的问题可以简化为这样一个事实，即我们需要从给定的列表 A 中发现(a,b)这样的对(a + b) mod 60 == 0。观察 #1：对于任何整数 x，(x mod 60) 位于 o 到 59 之间。初始化一个长度为 60 的数组，默认值设置为 0，其索引i将存储列表 A 中元素的数量，这样x mod 60 = i对于属于 A 的所有 xint freq[60] = {0};for(int i = 0; i < A.size(); i++)&nbsp; freq[(A[i] % 60)]++;现在再次迭代数组 A，对于每个 x，我们需要60 - (x mod 60)累积频率图中索引的计数，这将对应于它可以与之形成对的元素的数量。情况 where(x mod 60) == 30将是一个棘手的问题，这将要求我们从频率计数中减去 1。int ans = 0;for(int i = 0; i < A.size(); i++) {&nbsp; ans += freq[60 - (A[i] % 60)];&nbsp; if(A[i] % 60 == 30) ans--;}解决方案的整体复杂度为 O(n)。

Answer 2

想想散列、创建桶和模除法。所有可能的分钟将进入 60 个可能的桶之一。然后想想当您从任意两个存储桶中选择两个第二个值时，可以有多少种可能的组合。然后用 nC2 计数。这是我在 Java 中的解决方案。public int numPairsDivisibleBy60(int[] time) {&nbsp; &nbsp; int k = 60;&nbsp; &nbsp; int[] mods = new int[k];&nbsp; &nbsp; for (int i = 0; i < time.length; i++)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; mods[time[i] % k]++;&nbsp; &nbsp; // n(n-1)/2 pairs for multiples of k and numbers which leave remainder as half multiple of k&nbsp; &nbsp; int count = ((mods[0] * (mods[0] - 1)) / 2) +&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ((mods[k / 2] * (mods[k / 2] - 1)) / 2);&nbsp; &nbsp; for (int i = 1; i < k / 2; i++)&nbsp; &nbsp; &nbsp; &nbsp; count += mods[i] * mods[k - i];&nbsp; &nbsp; return count;}