如何不用嵌套循环判断Java数组中是否存在可整除所有元素的整数

开发者阿泽

2026-10-6

优化实现方案

核心思路

我们可以利用数组最大公约数（GCD）的性质实现线性时间复杂度的求解：
- 如果数组中存在某个元素可以整除其余所有整数，那么这个元素一定是整个数组的最大公约数
- 反过来，只要数组的最大公约数本身是数组中的元素，就满足题目要求，返回true，否则返回false

优化后代码

public class DivisibleCheck {
    // 求两个数的最大公约数（欧几里得算法）
    private static int gcd(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    // 求数组的最大公约数
    private static int arrayGcd(int[] arr) {
        int result = arr[0];
        for (int num : arr) {
            result = gcd(result, num);
            // 提前终止：GCD最小为1，无需继续计算
            if (result == 1) break;
        }
        return result;
    }

    public static boolean check(int[] arr) {
        if (arr.length == 0) return false; // 空数组可按业务需求调整返回值，这里默认返回false
        if (arr.length == 1) return true; // 单个元素必然满足条件
        int gcdOfArray = arrayGcd(arr);
        // 检查数组中是否存在等于GCD的元素
        for (int num : arr) {
            if (num == gcdOfArray) {
                return true;
            }
        }
        return false;
    }

    public static void main(String []args){
        int[] arr = {4,2,6,8};
        System.out.println(check(arr)); // 输出true

        int[] arr2 = {4,3,6,8};
        System.out.println(check(arr2)); // 输出false
    }
}