2022-05-19：给定一个数组arr，给定一个正数M，如果arr[i] + arr[j]可以被M整除，并且i ＜ j，那么(i,j)叫做一个M整除对。返

原创

福大大架构师每日一题

发布于 2022-05-19 19:41:30

1670

发布于 2022-05-19 19:41:30

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2022-05-19：给定一个数组arr，给定一个正数M，

如果arri + arrj可以被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;
}

执行结果如下：