计算列表中和能被60整除的元素对数量——优化时间复杂度

你的原解法逻辑正确，但**O(n²)**的时间复杂度在n=10000时会产生约5000万次循环操作（因为j从i+1开始，总次数是10000×9999/2≈5e7），虽然现代处理器算力强，但Java中循环的额外开销（比如List的元素访问、取模运算的成本）累加起来很容易触发超时，尤其是测试用例的时间限制通常比较严格。

要解决这个问题，我们可以利用模运算的性质把时间复杂度降到O(n)：两个数的和是60的倍数，等价于它们除以60的余数之和为0或60。具体来说：

• 余数为0的数，两两配对的和都是60的倍数
• 余数为30的数，两两配对的和也是60的倍数
• 对于余数r（1≤r≤29），每个余数r的数都能和余数(60-r)的数配对，它们的和是60的倍数

基于这个思路，优化后的代码如下：

public int getPairs(List<Integer> nums) {
    int[] remainderCounts = new int[60];
    // 统计每个余数出现的次数
    for (int num : nums) {
        int rem = num % 60;
        // 处理Java中负数取模的特殊情况（比如-1%60会得到-1，转成正余数59）
        if (rem < 0) {
            rem += 60;
        }
        remainderCounts[rem]++;
    }
    
    int result = 0;
    // 余数0的元素两两配对：组合数C(n,2) = n*(n-1)/2
    result += (long) remainderCounts[0] * (remainderCounts[0] - 1) / 2;
    // 余数30的元素两两配对，逻辑同上
    result += (long) remainderCounts[30] * (remainderCounts[30] - 1) / 2;
    
    // 处理1到29的余数，和对应的60-r余数配对
    for (int r = 1; r < 30; r++) {
        result += (long) remainderCounts[r] * remainderCounts[60 - r];
    }
    
    return result;
}

关键细节说明： #

• 负数余数处理：Java中负数取模的结果符号与被除数一致（比如-1 % 60 = -1），所以需要把负数余数转为正的，保证统计的余数范围在0-59之间。
• 避免整数溢出：计算组合数时，用long类型临时存储乘积，防止n较大时（比如余数0的元素有10000个）直接相乘导致int溢出。
• 时间效率：只需要遍历两次数据，第一次统计余数（O(n)），第二次计算配对数（仅循环30次，O(1)），总时间复杂度O(n)，10000个元素的情况下几乎瞬间完成。

你之前尝试转数组的优化只是减少了部分访问开销，但没有改变核心的O(n²)复杂度，所以无法解决超时问题。这种基于余数统计的思路才是这类“和为某数倍数”配对问题的标准高效解法。

内容的提问来源于stack exchange，提问作者f.khantsis