Leetcode 1250. Check If It Is a Good Array

[Woodyiiiiiii]

这道题考了数学的一个知识点：裴蜀定理，或者扩展欧几里得定理。也就是说，对于任意不全为0的整数a和b，满足x * a + y * b = k * gcd(a, b)，其中x和y为任意整数。这个推论也可以推广到任意多的整数。

所以这道题目中，要想在一个数组中找到一个子集，满足其特定和为1，则要满足这个子集中的元素的最大公约数为1。因为gcd不会增大，所以我们可以推导到整个数组的gcd都要为1。

import java.math.BigInteger;

class Solution {
    public boolean isGoodArray(int[] nums) {
        int gcd = nums[0];
        for (int i = 1; i < nums.length; i++) {
            gcd = BigInteger.valueOf(gcd).gcd(BigInteger.valueOf(nums[i])).intValue();
            if (gcd == 1) {
                return true;
            }
        }
        return gcd == 1;
    }
}

使用BigInteger的gcd函数虽然AC了，但耗时较大，所以可以自己写一个gcd方法。

class Solution {
    public boolean isGoodArray(int[] nums) {
        int gcd = nums[0];
        for (int i = 1; i < nums.length; i++) {
            gcd = myGcd(gcd, nums[i]); 
            if (gcd == 1) {
                return true;
            }
        }
        return gcd == 1;
    }

    private int myGcd(int a, int b) {
        if (a == 0) {
            return b;
        }
        return myGcd(b % a, a);
    }
}

快了很多，直接beats 100%。

---

• 1250. Check If It Is a Good Array
• 中文官方讲解