题目

有 N 个点位于一条线上，编号从 0 到 N-1 ，其坐标在数组 A 中给出。对于每个I (0 ≤ l <N)，直线上点数 I 的坐标为 A[l] 。点的坐标可能相同。

对于给定的整数 M ，如果子集内任意两个点之间的距离可被M整除，则称这些点的子集为M对齐。您的任务是查找给定 N 个点集的最大 M 对齐子集的大小。

例如，考虑整数 M=3 和数组 A，如下所示：

A[0] = -3 A[1] = -2 A[2] = 1 A[3] = 0 A[4] = 8 A[5] = 7 A[6] = 1

包含编号为1、2、5和6的点的子集，坐标分别为-2、1、7和1，是3对齐子集的示例，因为：

• 编号为1和2的点之间的距离为abs(A[1] - A[2]) = 3，
• 从5号点到编号1和2的点的距离分别为9和6，
• 从6号点到编号为1、2和5的点的距离分别为3、0和6，

这些距离都可以被 M=3 整除。此子集的大小为4，并且没有更大的3对齐子集。

编写一个函数:

int solution(int[] A, int M);

给定一个由 N 个整数和一个整数 M 组成的数组 A，返回最大 M 对齐子集的大小。

例如，给定 M=3 且 A=[-3，-2，1，0，8，7，1]，函数应返回4，如上所述；

给定 M=8 且 A=[7，1，11，8,4，10]，函数应返回1。

解

把所有按 M 的余数存成一组就可以，同组的刚好把余数消掉就是距离整除。返回最大即为所求。

注意：余数为负的，需要转为最小正余数（+M）

Java实现

int solution(int[] A, int M){
    //remainders[i] = j, 表示余数为i的频次是j
    int[] remainders = new int[M];
    int ans = 0; // 记录最大的频次
    int N = A.length;
    for(int i = 0; i < N; i++) {
        int remainder = A[i] % M;
        if(remainder < 0) {
            remainder += M;
        }
        remainders[remainder] ++;
        ans = Math.max(ans, remainders[remainder]);
    }
    return ans;
}

参考资料