1250. 检查「好数组」

难度

• Easy
• Medium
• Hard

思路

模拟几次不难发现，如果两个数互为质数，那么一定可以线性组合结果为 1 。所以我们要做的，就是判断数组中是否存在两个数互为质数。

显然，如果两两判断，一定超时。这时要想到，如果存在两个互为质数的数，那么整个数组的最大公因子一定是 1 ，反之则一定不是。那么，我们可以通过求整个数组的最大公因子来判断。假设初始 x = nums[0] ，不断更新 x = gcd(x, nums[i]) ，当 x == 1 时，说明数组的最大公因子为 1 ，直接返回 True 。如果正常退出循环，则返回 False 。

裴蜀定理：对于不全为零的任意整数 $a$ 和 $b$，记 $g = \gcd(a,b)$ ，其中 $\gcd(a, b)$ 为 $a$ 和 $b$ 的最小公约数，则对于任意整数 $x$ 和 $y$ 都满足 $a \times x + b \times y$ 是 $g$ 的倍数，特别地，存在整数 $x$ 和 $y$ 满足 $a \times x + b \times y = g$ 。

代码

def gcd(x, y) -> int:
    if x < y:
        x ^= y
        y ^= x
        x^= y
    if y:
        x = x % y
        return gcd(y, x)
    else:
        return x

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        x = nums[0]
        for num in nums:
            x = gcd(x, num)
            if x == 1:
                return True
        return False

官解超精简版

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        return reduce(gcd, nums) == 1

其中 gcd 函数是 math 库求最大公因数的函数。

reduce 函数的作用在于施加一个两参数的函数到一个可迭代对象上。举例来说， reduce(lambda: x, y: x + y, [1, 2, 3, 4]) 等价于计算 (((1 + 2) + 3 ) + 4) 并返回。