LeetCode 1250 检查好数组：裴蜀定理 3 行代码解决，时间复杂度 O(n log M)

LeetCode 1250 检查好数组：裴蜀定理的实战应用与算法优化

在算法竞赛和编程面试中，数论问题往往因其独特的思维方式和简洁的数学解法而备受青睐。今天我们要探讨的LeetCode 1250题"检查好数组"，就是一个典型的数论问题，其核心在于理解并应用裴蜀定理（Bézout's Lemma）。这道题不仅考察了对基础数论知识的掌握，更考验了将数学定理转化为高效算法的能力。

1. 问题解析与数学基础

1.1 问题描述

题目给出一个正整数数组nums，要求判断是否存在一个非空子集，其中每个元素乘以任意整数后相加的和等于1。如果存在这样的子集，则称原数组为"好数组"，返回True；否则返回False。

例如：

• 输入nums = [12,5,7,23]，输出True（因为5×(-2) + 7×3 = 1）
• 输入nums = [4,6,8,10]，输出False

1.2 裴蜀定理简介

裴蜀定理（又称贝祖定理）是解决这个问题的关键。该定理表明：

对于不全为零的整数a和b，存在整数x和y使得ax + by = gcd(a,b)。特别地，当a和b互质时（gcd(a,b)=1），存在x和y使ax + by = 1。

这个定理可以推广到多个整数的情况：

• 对于n个整数a₁,a₂,...,aₙ，存在整数x₁,x₂,...,xₙ使得x₁a₁ + x₂a₂ + ... + xₙaₙ = gcd(a₁,a₂,...,aₙ)
• 因此，这些数的线性组合能得到1当且仅当它们的最大公约数为1

1.3 问题转化

根据裴蜀定理，原问题可以转化为：

• 检查数组中所有元素的整体最大公约数是否为1
• 如果是，则存在满足条件的子集；否则不存在

这种转化将看似复杂的组合问题简化为一个简单的最大公约数计算问题。

2. 算法设计与实现

2.1 基本思路

基于上述分析，算法步骤如下：

1. 计算数组中所有元素的整体最大公约数（gcd）
2. 判断该gcd是否等于1

计算多个数的gcd可以通过迭代方式实现：

• 初始gcd为第一个数
• 依次计算当前gcd与下一个数的gcd，更新当前gcd
• 如果在过程中gcd变为1，可以提前终止（因为1是最小的可能gcd）

2.2 代码实现

以下是Python的实现示例：

import math from functools import reduce def isGoodArray(nums): def compute_gcd(a, b): while b: a, b = b, a % b return a overall_gcd = nums[0] for num in nums[1:]: overall_gcd = compute_gcd(overall_gcd, num) if overall_gcd == 1: break return overall_gcd == 1 # 更简洁的实现方式 def isGoodArray_short(nums): return reduce(math.gcd, nums) == 1

2.3 复杂度分析

• 时间复杂度：O(n log M)，其中n是数组长度，M是数组中的最大数
  • 每次gcd计算的时间复杂度为O(log min(a,b))
  • 最坏情况下需要计算n-1次gcd
• 空间复杂度：O(1)，只使用了常数额外空间

3. 算法优化与边界处理

3.1 优化策略

1. 提前终止：一旦计算过程中gcd变为1，可以立即返回True
2. 特殊值处理：
   • 如果数组包含1，直接返回True（因为1×1 = 1）
   • 如果数组长度为1，只需检查该数是否为1

3.2 边界情况

需要考虑的特殊情况包括：

• 空数组（根据题意不会出现）
• 单元素数组[1]
• 包含重复元素的数组
• 所有元素相同的情况

优化后的实现：

def isGoodArray_optimized(nums): if 1 in nums: return True current_gcd = nums[0] for num in nums[1:]: current_gcd = math.gcd(current_gcd, num) if current_gcd == 1: return True return current_gcd == 1

4. 数学原理深入探讨

4.1 裴蜀定理的证明概要

虽然在实际解题中不需要自行证明裴蜀定理，但理解其证明有助于深入掌握：

1. 考虑集合S = {ax + by | x,y ∈ ℤ}中的最小正整数d
2. 证明d是a和b的公约数
3. 证明d是最大的公约数（任何公约数都整除d）
4. 因此d = gcd(a,b) ∈ S

4.2 扩展欧几里得算法

裴蜀定理的构造性证明引出了扩展欧几里得算法，它不仅能计算gcd，还能找到满足ax + by = gcd(a,b)的整数x和y。

算法实现示例：

def extended_gcd(a, b): if b == 0: return (1, 0, a) else: x, y, gcd = extended_gcd(b, a % b) return (y, x - (a // b) * y, gcd)

4.3 多变量推广

对于n个变量a₁,a₂,...,aₙ，裴蜀定理依然成立： gcd(a₁,a₂,...,aₙ) = min{∑xᵢaᵢ | xᵢ ∈ ℤ, ∑xᵢaᵢ > 0}

这解释了为什么我们可以通过计算整个数组的gcd来解决问题。

5. 实际应用与相关问题

5.1 典型应用场景

裴蜀定理在以下场景中有重要应用：

1. 解线性丢番图方程
2. 计算模反元素（用于RSA加密等）
3. 证明数论中的各种命题
4. 算法竞赛中的组合数学问题

5.2 相关LeetCode题目

1. 365. Water and Jug Problem：利用裴蜀定理判断是否能量出特定容量的水
2. 780. Reaching Points：判断能否通过特定操作从起点到达终点
3. 2543. Check if Point Is Reachable：类似的坐标可达性问题

5.3 进阶挑战

对于想进一步挑战的读者，可以尝试：

1. 找出实际满足条件的系数（而不仅仅是判断存在性）
2. 处理超大数情况下的效率问题
3. 研究裴蜀定理在多项式环中的推广

6. 常见误区与调试技巧

6.1 常见错误

1. 误认为只需要检查相邻元素的gcd
2. 忽略数组中已经存在1的特殊情况
3. 错误处理所有元素相同且不为1的情况

6.2 调试建议

1. 从小规模测试用例开始：
   • [1] → True
   • [2,4] → False
   • [3,5] → True
2. 打印中间计算结果，观察gcd的变化过程
3. 对比标准数学库的gcd计算结果

7. 性能对比与语言特性

7.1 不同语言实现

7.2 性能优化对比

在实际面试或竞赛中，掌握裴蜀定理及其应用可以显著提升解决数论问题的效率。这道LeetCode题目虽然表面简单，但深入理解其数学背景能为解决更复杂的问题奠定坚实基础。