2022-05-19：给定一个数组arr，给定一个正数M， 如果arr[i] + arr[j]可以被M整除，并且i < j，那么(i,j)叫做一个M整除对。 返回arr中M整除对的总数量。 来自微软。

答案2022-05-19：

求余，答案叠加，次数叠加。 时间复杂度：O(N)。 空间复杂度：O(M)。

代码用rust编写。代码如下：

fn main() {
    let arr: Vec<isize> = vec![5, 5, 5];
    let ans = num2(&arr, 5);
    println!("ans = {}", ans);
}

fn num2(arr: &Vec<isize>, m: isize) -> isize {
    let n = arr.len() as isize;
    let mut cnts: Vec<isize> = vec![];
    for _i in 0..m {
        cnts.push(0);
    }
    let mut ans: isize = 0;
    let mut i: isize = n - 1;
    while i >= 0 {
        let cur = (arr[i as usize] % m + m) % m;
        ans += cnts[((m - cur) % m) as usize];
        cnts[cur as usize] += 1;
        i -= 1;
    }
    return ans;
}

执行结果如下：

在这里插入图片描述

左神java代码