数组中两两元素的最大GCD求解超时，求高效优化方案

原代码采用双重循环枚举所有数对计算GCD，时间复杂度为O(n²)，当数组规模较大（比如元素数量超过10^4）时，会因计算量过大导致超时。

优化思路 #

• 数组中两两元素的最大GCD不可能超过数组中的最大值，因此我们可以从最大值开始向下遍历，寻找第一个能整除数组中至少两个元素的数，这个数就是答案。
• 用计数数组统计每个数的出现次数，再通过倍数累加的方式快速判断某个数的倍数在数组中的总数量，避免枚举所有数对。

优化后的代码 #

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] nums = new int[n];
        int maxVal = 0;

        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
            if (nums[i] > maxVal) {
                maxVal = nums[i];
            }
        }

        int result = findMaxGCD(nums, maxVal);
        System.out.println(result);
    }

    public static int findMaxGCD(int[] arr, int maxVal) {
        // 计数数组，统计每个数出现的次数
        int[] count = new int[maxVal + 1];
        for (int num : arr) {
            count[num]++;
        }

        // 从最大值开始往下找
        for (int d = maxVal; d >= 1; d--) {
            int multipleCount = 0;
            // 统计所有d的倍数的数量，提前终止减少计算
            for (int multiple = d; multiple <= maxVal; multiple += d) {
                multipleCount += count[multiple];
                if (multipleCount >= 2) {
                    break;
                }
            }
            if (multipleCount >= 2) {
                return d;
            }
        }
        // 数组元素全为1等极端情况，返回1
        return 1;
    }
}

代码说明 #

• 计数数组：遍历原数组统计每个数的出现次数，快速获取任意数的存在情况。
• 从大到小遍历：从数组最大值开始检查，第一个满足“至少两个元素是其倍数”的数就是最大GCD，找到后直接返回，无需后续计算。
• 倍数统计优化：对每个d，累加其倍数的计数，一旦计数≥2就跳出内层循环，减少不必要的运算。

时间复杂度分析 #

优化后的时间复杂度为O(max_val log max_val)，因为内层循环对每个d的遍历次数是max_val/d，总和为max_val*(1 + 1/2 + 1/3 + ... + 1/max_val)，该和属于O(log max_val)级别。当数组元素数量大但最大值未过度增长时，效率远高于原O(n²)实现。

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