精读《算法题 - 统计可以被 K 整除的下标对数目》

今天我们看一道 leetcode hard 难度题目：统计可以被 K 整除的下标对数目。

题目

给你一个下标从 0 开始、长度为 n 的整数数组 nums 和一个整数 k ，返回满足下述条件的下标对 (i, j) 的数目：

• 0 <= i < j <= n - 1 且
• nums[i] * nums[j] 能被 k 整除。

示例 1：

输入：nums = [1,2,3,4,5], k = 2
输出：7
解释：
共有 7 对下标的对应积可以被 2 整除：
(0, 1)、(0, 3)、(1, 2)、(1, 3)、(1, 4)、(2, 3) 和 (3, 4)
它们的积分别是 2、4、6、8、10、12 和 20 。
其他下标对，例如 (0, 2) 和 (2, 4) 的乘积分别是 3 和 15 ，都无法被 2 整除。  

思考

首先想到的是动态规划，一个长度为 n 的数组结果与长度为 n-1 的关系是什么？

首先 n-1 时假设算好了一个结果 result，那么长度为 n 时，新产生的匹配是下标 [0, n-1] 与下标 n 数字的匹配关系，假设这些关系中有 q 个满足题设，则最终答案是 result + q。

这种想法适合 (i, j) 满足任意关系的题目，代码如下：

function countPairs(nums: number[], k: number): number {
  if (nums.length < 2) {
    return 0
  }

  const dpCache: Record<number, number> = {}

  for (let i = 1; i < nums.length; i++) {
    switch (i) {
      case 1:
        if (nums[0] * nums[1] % k === 0) {
          dpCache[1] = 1    
        } else {
          dpCache[1] = 0
        }
        break
      default:
        // [0,i-1] 洗标范围内与 i 下标组合，看看有多少种可能
        let currentCount = 0
        for (let j = 0; j <= i - 1; j++) {
          if (nums[j] * nums[i] % k === 0) {
            currentCount++
          }
        }
        dpCache[i] = dpCache[i - 1] + currentCount
    }
  }

  return dpCache[nums.length - 1]
};

很可惜超时了，因为回头想想，虽然思路是 dp，但本质上是暴力解法，时间复杂度是 O(n²)。

为了 AC，必须采用更低复杂度的算法。

利用最大公约数解题

如果只循环一次数组，那么必须在循环到数组每一项的时候，就能立刻知道该项与其他哪几项的乘积符合 nums[i] * nums[j] 能被 k 整除，这样的话累加一下就能得到答案。

也就是说，拿到数字 nums[i] 与 k，我们要知道有哪些 nums[j] 是满足要求的。

当然，如果把所有剩余数字循环一遍来找满足条件的 nums[j]，那时间复杂度就还是 O(n²)，但不循环似乎无法继续思考了，这道题很容易在这里陷入僵局。

接下来就要发散思维了，先想这个问题：满足条件的 nums[j] 要满足 nums[i] * nums[j] % k === 0，那除了通过遍历把每一项 nums[j] 拿到真正的算一遍之外，还有什么更快的办法呢？

除了真的算一下之外，想想 nums[j] 还要具备什么特性？这个特性最好和倍数有关，因为如果我们计算所有数字倍数出现的个数，时间复杂度会比较低。

nums[i] 与 k 的最大公约数就满足这个条件，因为我们希望的是 nums[j] * nums[i] 是 k 的倍数，那么 nums[j] 最小的值就是 k / nums[i]，但这个除出来可能不是整数，那必须保证 k 除以的数字是一个整数，这个除数用 nums[i] 与 k 的最大公约数最划算。nums[j] 可以更大，只要是这个结果的倍数就行了，总结一下，nums[j] 要满足是 k / gcd(nums[i], k) 的倍数。

再重点解释下原因，我们假设 nums[i] = 2, k=100，此时是 k 比较大的情况，那么其最大公约数一定小于等于 nums[i]，因此 k / 最大公约数 * nums[j] 得到的数字一定大于 k / nums[i] * nums[j]，毕竟最大公约数比 nums[i] 小嘛，而 k / nums[i] * nums[j] 就是不考虑 nums[j] 是整数情况下让 k 可以整除 nums[i] * nums[j] 时，nums[j] 取的最小值的情况，因此 nums[j] 只要是 k / 最大公约数 的倍数就行了。

反之，如果 k 比 nums[i] 小，比如 nums[i] = 100, k=2，此时最大公约数是小于等于 k 的，但用一个比 k 还要大的 nums[i] 作为乘法的一边，乘出来的结果肯定大于 k，所以不用担心 nums[i] * nums[j] < k 的情况，所以 nums[j] 只要是 k / 最大公约数 的倍数就行了。

综上，无论如何 nums[j] 只要是 k / 最大公约数 的倍数就行了。

所以对于每一个 nums[i]，我们能快速计算出 x = k / gcd(nums[i], k)，接下来只要找到 nums 所有数字中，是 x 倍数的有多少累加起来就行了。这一步也不能鲁莽，因为数组长度非常大，性能更好的方案是：先从1开始到最大值，计算出每个数字的倍数有几个，存在一个 map 表里，之后找倍数有几个直接从 map 表里获取就行了。

比如有数字 1 ~ 10，我们要计算每个数字的倍数出现了几次，大概是这么算的：

• 1,2,3... 数到 10，那么 1 的倍数有 10 个数字。
• 2,4,6,8,10 数 5 次，那么 2 的倍数有 5 个数字。
• 3,6,9 数 3 次，那么 3 的倍数有 3 个数字。

以此类推，我们发现一个规律，即对于长度为 n 的数组，要数的总次数为 n + n/2 + n/3 + ... + 1，这是一个调和数列，具体怎么证明的笔者已经忘了，但可以记住它的值趋向于欧拉常数 + ln(n+1)，这就是要数的次数，所以用这个方案，整体时间复杂度是 O(nlnn)，比 O(n²) 小了很多。

所以我们只要 “暴力” 的从 1 开始到 nums 最大的数字，把所有数字的倍数都提前计算出来，最后的时间复杂度反而会更小，这是非常神奇的结论。为了避免计算多余的倍数关系，反而时间复杂度是 O(n²)，而暴力计算所有数字倍数的时间复杂度竟然是 O(nlnn)，这个可以背下来。

接下来就简单了，直接上代码。

用 js 实现 gcd（最大公约数）计算可以用辗转相除法：

function gcd(left: number, right: number) {
    return right === 0 ? left : gcd(right ,left % right)
}

整体代码实现：

function countPairs(nums: number[], k: number): number {
    // nums 最大的数字
    let max = 0
    nums.forEach(num => max = Math.max(num, max))

    // Map<数字x, 数字x 倍数在 nums 中出现的次数>
    const mutipleMap: Record<number, number> = {}

    // 先遍历一次 nums，将其倍数次自增
    nums.forEach(num => {
        if (mutipleMap[num] === undefined) {
            mutipleMap[num] = 1
        } else {
            mutipleMap[num]++
        }
    })

    // 按以下规律数倍数出现的次数，但忽略自身
    // 1,2,3...,max
    // 2,4,6...,max
    // 3,6,9...,max
    for (let i = 1; i <= max; i++) {
        for (let j = i * 2; j <= max; j+=i) {
            if (mutipleMap[i] === undefined) {
                mutipleMap[i] = 0
            }
            mutipleMap[i] += mutipleMap[j] ?? 0
        }
    }

    // 答案
    let result = 0

    // k / gcd(num, k) 的数组出现的次数累加
    nums.forEach(num => {
        const targetMutiple = k / gcd(num, k)
        result += mutipleMap[targetMutiple] ?? 0
    })

    // 排除自己乘以自己满足条件的情况
    nums.forEach(num => {
        if (num * num % k === 0) { result-- }
    })
    
    return result / 2
};

有几个注意要点。

第一个是 for (let j = i * 2，之所以要乘以 2，是因为在前面遍历 nums 时，自己的倍数已经被算过一次，比如 3,6,9 的 3 已经被初始化算过一次，所以从 3*2=6 开始就行了。

第二个是 mutipleMap[i] += mutipleMap[j]，比如 i=3，j=9 时，因为 9 是 3 的倍数，所以此时 3 的倍数可以继承 9 的倍数的数量，而数字是不断变大的，所以不会重复。

第三个是 if (num * num % k === 0) { result-- }，因为题目要求 0 <= i < j <= n - 1，但我们计算倍数时，比如 9 是 3 的倍数，但 9 可以通过 3 * 3 得到，这种不合规的数据要过滤掉。

第四个是 return result / 2，因为在最后累加次数时，把每个数字与其他数字都判断了一遍，假设 1, 3 是合法的，那么 3, 1 也肯定是合法的，但因为 i < j 的要求，我们要把 3, 1 干掉，所有合法的结果都存在顺序颠倒的 case，所以除以 2.

总结

这道题很容易栽在动态规划超时的坑上面，要解决此题需要跨越两座大山：

1. 想到最大公约数与另一个数字之间的关系。
2. 意识到暴力计算倍数的时间复杂度是 O(nlnn)。

最后，本题还隐含了 n + n/2 + n/3 + ... + 1 为什么极限是 O(nlnn) 的知识，背后有一个 调和数列 的大知识背景，感兴趣的同学可以深入了解。

讨论地址是：精读《算法 - 统计可以被 K 整除的下标对数目》· Issue #495 · dt-fe/weekly