求可被n整除的相邻元素和的最大数量的高效解法

给定一个整数数组，找出其中可被n整除的连续子数组和的总数量。

示例 #

• 示例1：

  input: long[] array = [1, 2, 3], n = 7
  output: 0

• 示例2：

  input: long[] array = [1, 2, 4], n = 7
  output: 1

• 示例3：

  input: long[] array = [2, 1, 2, 1, 1, 2, 1, 2], n = 4
  output: 6

约束条件 #

• 数组长度固定为50000
• 数组元素值 ≤ 2^31 - 1
• n ≤ 2^31 - 1

当前问题代码 #

你提供的代码是暴力枚举所有可能的连续子数组，时间复杂度为O(n²)，在数组长度为50000时必然触发CPU超时：

public static int maxSums(long[] array, long n) {

        int count = 0;

        if (array.length == 1 && array[0] == n) {
            return 1;
            
        } else {
            for (int i = 0; i < array.length; i++) {
                long sum = 0;
                for (int j = i; j < array.length; j++) {
                    sum += array[j];
                    if (sum % n == 0) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

O(n)复杂度的优化解法 #

核心思路是前缀和+哈希表统计余数频率，逻辑非常直接：

1. 计算前缀和：从数组开头到当前元素的总和；
2. 若两个前缀和除以n的余数相同，它们的差（即中间那段子数组的和）必然能被n整除；
3. 用哈希表记录每个余数出现的次数，每碰到一个余数，就把之前该余数出现的次数加到结果里——每一次之前的出现都对应一个符合条件的子数组；
4. 初始时要把余数0的计数设为1，因为如果某个前缀和本身就能被n整除，这个从开头到当前位置的子数组要算进去。

代码实现 #

import java.util.HashMap;
import java.util.Map;

public static int maxSumsOptimized(long[] array, long n) {
    // 题目中n应为正整数，这里做基础校验
    if (n <= 0) {
        return 0;
    }

    Map<Long, Integer> remainderMap = new HashMap<>();
    // 初始前缀和为0，对应余数0出现1次
    remainderMap.put(0L, 1);

    long prefixSum = 0;
    int result = 0;

    for (long num : array) {
        prefixSum += num;
        // 处理负数余数，确保余数非负
        long remainder = prefixSum % n;
        if (remainder < 0) {
            remainder += n;
        }

        // 累加之前出现过的相同余数的次数
        if (remainderMap.containsKey(remainder)) {
            result += remainderMap.get(remainder);
        }

        // 更新当前余数的计数
        remainderMap.put(remainder, remainderMap.getOrDefault(remainder, 0) + 1);
    }

    return result;
}

关键细节 #

• 时间复杂度：O(n)，仅需遍历数组一次，哈希表的存取操作均为O(1)；
• 空间复杂度：O(min(n, 50000))，最多存储n个不同的余数；
• 负数处理：Java中负数取模会得到负数余数，需加n转为非负，保证统计准确；
• 初始状态：必须提前放入余数0的计数，否则会漏掉从数组开头就符合条件的子数组（比如示例2的总和7，余数0，此时初始的1次会被累加，得到正确结果1）。

验证示例3 #

以示例3的数组[2,1,2,1,1,2,1,2]和n=4为例：
前缀和依次为2、3、5、6、7、9、10、12，对应的余数是2、3、1、2、3、1、2、0。
哈希表的变化和结果累加过程：

• 初始：{0:1}
• 余数2：未出现过，结果不变，哈希表更新为{0:1, 2:1}
• 余数3：未出现过，结果不变，哈希表更新为{0:1,2:1,3:1}
• 余数1：未出现过，结果不变，哈希表更新为{0:1,2:1,3:1,1:1}
• 余数2：之前出现1次，结果+1（当前=1），哈希表更新为{0:1,2:2,3:1,1:1}
• 余数3：之前出现1次，结果+1（当前=2），哈希表更新为{0:1,2:2,3:2,1:1}
• 余数1：之前出现1次，结果+1（当前=3），哈希表更新为{0:1,2:2,3:2,1:2}
• 余数2：之前出现2次，结果+2（当前=5），哈希表更新为{0:1,2:3,3:2,1:2}
• 余数0：之前出现1次，结果+1（当前=6），哈希表更新为{0:2,2:3,3:2,1:2}
  最终结果为6，与示例3完全一致。

内容的提问来源于stack exchange，提问作者Enzo