难度: Hard
给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。
假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。
示例 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 <= nums.length <= 10^51 <= nums[i] <= 10^9运行时间: 36 ms
内存: 25.3 MB
from math import gcd
from typing import List
class Solution:
def isGoodArray(self, nums: List[int]) -> bool:
# 初始化最大公约数为 0
g = 0
# 遍历数组中的每个数
for num in nums:
# 使用 gcd 函数更新最大公约数
g = gcd(g, num)
# 如果最大公约数为 1，则可以提前返回 True
if g == 1:
return True
# 返回最大公约数是否为 1
return g == 1
solution = Solution()
print(solution.isGoodArray([12, 5, 7, 23])) # 输出: True
print(solution.isGoodArray([29, 6, 10])) # 输出: True
print(solution.isGoodArray([3, 6])) # 输出: False
这道题的核心思路是利用贝祖定理（Bézout's identity），该定理指出对于任意整数a和b，如果d是它们的最大公约数，那么一定存在整数x和y，使得ax + by = d。根据这个定理，如果数组中所有元素的最大公约数为1，那么就可以通过这些元素的线性组合得到1，即存在一种组合使得最终和为1。因此，我们只需要计算数组中所有数的最大公约数是否为1即可。实现上，我们从数组的第一个元素开始，依次计算与下一个元素的最大公约数，直到遍历完整个数组，如果过程中最大公约数变为1，就可以提前结束遍历返回True。如果遍历完成后最大公约数仍然是1，则返回True，否则返回False。
时间复杂度: O(n * logN)
空间复杂度: O(1)
from math import gcd
from typing import List
class Solution:
def isGoodArray(self, nums: List[int]) -> bool:
# 初始化最大公约数为 0
g = 0
# 遍历数组中的每个数
for num in nums:
# 使用 gcd 函数更新最大公约数
g = gcd(g, num)
# 如果最大公约数为 1，则可以提前返回 True
if g == 1:
return True
# 返回最大公约数是否为 1
return g == 1
solution = Solution()
print(solution.isGoodArray([12, 5, 7, 23])) # 输出: True
print(solution.isGoodArray([29, 6, 10])) # 输出: True
print(solution.isGoodArray([3, 6])) # 输出: False
在使用贝祖定理来判断一个数组是否是「好数组」时，理论上并不需要所有元素都参与gcd的计算。如果数组中某个子集的元素的最大公约数为1，那么整个数组的最大公约数也必然为1。这是因为，如果子集的最大公约数为1，根据贝祖定理，可以找到这些元素的整数倍组合，其和为1。添加更多的其他元素并不会使得这个gcd变得更大。因此，虽然理论上不需要所有元素参与，但在算法实现中通常会遍历所有元素以保证全面性和简化程序逻辑。
一旦在计算过程中得到gcd为1，就不可能通过添加更多的元素使gcd改变为非1的值。这是由最大公约数的性质决定的：如果一组数的最大公约数为1，那么任何添加的数的最大公约数仍会是1，因为1是所有整数的公约数。因此，当我们在计算过程中得到gcd为1时，可以确信无论如何添加更多的数，这个gcd不会改变，所以提早返回True是合理的。
在计算最大公约数时，初始化g为0是因为0与任何数n的最大公约数是n本身。这样的初始化方式允许我们从一个中立的基点开始累计计算最大公约数，不受数组起始元素的约束。这种方法简化了代码实现，使得gcd函数可以统一处理数组中的所有元素而不需要特别处理第一个元素。
是的，如果数组中包含1，则可以直接返回True。由于任何数与1的最大公约数必定为1，包含1的数组的最大公约数自然也是1。这意味着可以通过组合中至少包含一个1的方式，根据贝祖定理得出总和为1的组合，从而证明该数组是「好数组」。因此，在算法实现中，检测到1即可立即返回True，这是一个优化步骤。