Divisible Sum Pairs 可除和对

看不太懂,先留着

可除数和对 | HackerRank — Divisible Sum Pairs | HackerRank

给定一个整数数组和一个正整数k ，求(i,j) 对中i<j和ar[i] +ar[j] 能被k整除的个数。

function divisibleSumPairs(n: number, k: number, ar: number[]): number {
    // Write your code here
    let count = 0
    const remainderCount = new Array(k).fill(0)
    for(let i=0;i<n;i++){
        const remainder = ar[i] % k
        const neededRemainder = (k -remainder) % k
        count += remainderCount[neededRemainder]
        remainderCount[remainder]++
    }
    return count
}

• count: 用于记录满足条件的数对的数量，初始值设为 0。

• remainderCount: 用于存储余数的出现次数。长度为 k 的数组，初始时所有值为 0。其目的在于记录每个余数（0 到 k-1）的出现次数，方便后续查找。

• const remainder = ar[i] % k; 计算当前元素 ar[i] 对 k 的余数，这样可以确定这个数在模 k 的情况下的分类。

• const neededRemainder = (k - remainder) % k;

• 通过上面的公式，我们可以确定要与当前数ar[i]配对的另一个数的余数：

  如果 remainder 是 0，neededRemainder 也是 0，这意味着另一个数也应该是 0（即 ar[j] 的余数为 0）。

  如果 remainder 是 1 且 k 是 5，则 neededRemainder 是 4，这意味着要找的另一个数的余数应该是 4，以使得它们的和（即 1 + 4）能够被 5 整除。

• 更新 count:

  • count += remainderCount[neededRemainder]：这一步的作用是，如果当前数的余数为 remainder，我们通过查找 remainderCount 数组来获取之前有多少个数的余数是 neededRemainder。这些数可以和当前数成对，从而构成符合条件的和。

• 更新 remainderCount:

  • remainderCount[remainder]++：这行代码是将当前数的余数 remainder 的计数加 1，因为我们在处理完当前数后，希望将它也加入到余数的计数中，供后续的元素使用。