1250. 检查「好数组」

ITCharge大约 4 分钟

---

1250. 检查「好数组」

标签：数组、数学、数论
难度：困难

题目大意

描述：给定一个正整数数组 $nums$ 。你需要从中任选一些子集，然后将子集中的每个数乘以任意整数（可正可负可为 $0$ ），再求和。如果存在一种选法和系数使得和为 $1$ ，那么这个数组就是「好数组」。

要求：判断数组是否为好数组，返回 True 或 False。

说明：

$1 \le nums.length \le 10^5$ 。
$1 \le nums[i] \le 10^9$ 。

示例：

示例 1：

输入：nums = [12,5,7,23]
输出：true
解释：挑选数字 5 和 7。
5*3 + 7*(-2) = 1

示例 2：

输入：nums = [29,6,10]
输出：true
解释：挑选数字 29, 6 和 10。
29*1 + 6*(-3) + 10*(-1) = 1

示例 3：

输入：nums = [3,6]
输出：false

解题思路

思路 1：裴蜀定理 + 最大公约数

1. 核心思想

这道题背后是一个经典的数论定理——裴蜀定理（Bézout's Theorem）。

裴蜀定理说的是：对于两个整数 $a$ 和 $b$ ，一定存在整数 $x$ 和 $y$ （可以是负数），使得 $ax + by = \gcd(a, b)$ 。也就是说，两个数的线性组合能得到的最小正整数就是它们的最大公约数。

更一般地，**一组整数 $a_1, a_2, ..., a_k$ 的线性组合能得到的所有值，一定是它们最大公约数 $g$ 的倍数，而且一定能得到 $g$ 本身。**换句话说，这些数能组合出 $1$ ，当且仅当它们的最大公约数是 $1$ 。

为什么？因为线性组合能得到的值的集合 $S = \\{a_1x_1 + a_2x_2 + ... + a_kx_k \mid x_i \in \mathbb{Z}\\}$ ，其实就是 $g \cdot \mathbb{Z} = \\{g \times t \mid t \in \mathbb{Z}\\}$ 。如果 $g = 1$ ，那么 $1 \in S$ ；如果 $g \neq 1$ ， $1 \notin S$ 。

2. 具体步骤

第 1 步：初始化最大公约数

将当前最大公约数 $g$ 初始化为数组第一个元素 $nums[0]$ 。

第 2 步：逐个求最大公约数

从第二个元素开始遍历数组，每次将当前元素与当前 $g$ 求最大公约数，更新 $g$ 。

第 3 步：提前剪枝

如果某一步 $g$ 已经变成了 $1$ ，直接返回 True。因为 $g = 1$ 后，继续和后面的数求最大公约数，结果一定还是 $1$ 。

第 4 步：返回结果

遍历结束后，判断 $g$ 是否等于 $1$ ，返回 g == 1。

结合示例走一遍：

$nums = [12,5,7,23]$

$g = \gcd(12, 5) = 1$ ，直接返回 True。

$nums = [3,6]$

$g = \gcd(3, 6) = 3$ ，遍历结束， $3 \neq 1$ ，返回 False。确实， $3$ 和 $6$ 的任何线性组合都是 $3$ 的倍数，不可能得到 $1$ 。

3. 为什么这样是对的

有人可能会问：「裴蜀定理说的是两个数的情况，扩展到多个数是否仍然成立？」

答案是成立的。我们可以递归地看：设 $g_2 = \gcd(a_1, a_2)$ ，那么 $a_1$ 和 $a_2$ 的组合能表示出 $g_2$ 。接着 $g_3 = \gcd(g_2, a_3) = \gcd(a_1, a_2, a_3)$ ，而 $a_1, a_2, a_3$ 的组合也能表示出 $g_3$ （因为可以用 $g_2$ 的倍数加上 $a_3$ 的倍数得到 $g_3$ ）。依此类推，所有数的最大公约数 $g$ 一定能被它们的线性组合表示出来。所以 $g$ 是否为 $1$ 就是充要条件。

思路 1：代码

import math

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        # 第 1 步：初始化为第一个元素
        g = nums[0]

        # 第 2 步：逐个求最大公约数
        for num in nums[1:]:
            g = math.gcd(g, num)
            # 第 3 步：提前结束
            if g == 1:
                return True

        # 第 4 步：检查最终结果
        return g == 1

思路 1：复杂度分析

时间复杂度： $O(n \log \max(nums))$ ，其中 $n$ 是数组 $nums$ 的长度， $\max(nums)$ 是数组中的最大值。每次计算最大公约数使用欧几里得算法，时间复杂度为 $O(\log \min(a, b))$ 。在本题中 $nums[i] \le 10^9$ ，所以 $\log$ 部分约 $30$ 次运算，整体非常快。
空间复杂度： $O(1)$ ，只使用了常数个变量。