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

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 的所有 x

int freq[60] = {0};

for(int i = 0; i < A.size(); i++)

  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++) {

  ans += freq[60 - (A[i] % 60)];

  if(A[i] % 60 == 30) ans--;

}

解决方案的整体复杂度为 O(n)。

Answer 2

想想散列、创建桶和模除法。所有可能的分钟将进入 60 个可能的桶之一。然后想想当您从任意两个存储桶中选择两个第二个值时，可以有多少种可能的组合。然后用 nC2 计数。这是我在 Java 中的解决方案。

public int numPairsDivisibleBy60(int[] time) {

    int k = 60;

    int[] mods = new int[k];

    for (int i = 0; i < time.length; i++) 

        mods[time[i] % k]++;

    // n(n-1)/2 pairs for multiples of k and numbers which leave remainder as half multiple of k

    int count = ((mods[0] * (mods[0] - 1)) / 2) +

                ((mods[k / 2] * (mods[k / 2] - 1)) / 2);

    for (int i = 1; i < k / 2; i++)

        count += mods[i] * mods[k - i];

    return count;

}