LeetCode 题解：1250. 检查「好数组」，裴蜀定理，详细注释

作者：Lee Chen

2024-08-15
福建
本文字数：1050 字
阅读完需：约 3 分钟

原题链接：https://leetcode.cn/problems/check-if-it-is-a-good-array/

关于裴蜀定理：

裴蜀定理是关于最大公约数的定理
裴蜀定理的含义为：如果有不全为 0 的整数a和b，它们的最大公约数为g，那么对任意整数x和y，都满足x * a + y * b = n * g，n为整数。
裴蜀定理的推论：如果有整数a1, a2, ...an，其中有任意两个数是互质（最大公约数为 1）的，那么就存在整数x1, x2, ...xn，使得x1 * a1 + x2 * a2 + ...xn * an=1（参考n个整数间的裴蜀定理）

使用欧几里得算法计算最大公约数：

如果有两个数a和0，那么它们的最大公约数是a
如果有两个数42和18，它们的最大公约数是g
由于42 % 18 = 24，42可以拆分为18和24。由于42可以被g整除，18也可以被g整除，那么24也一定可以被g整除。那么，问题就被转换为了求24和18的最大公约数
24和18可以转换成18和6
18和6可以转换成12和6
12和6可以转换成6和6
6和6可以转换成6和0
最后可求得42和18的最大公约数为6

将欧几里得算法转换成代码：

方法一：递归

const gcd = (num1, num2) => {  return num1 === 0 ? num2 : gcd(num2 % num1, num1)}

复制代码

方法二：迭代

const gcd = (num1, num2) => {  while (num1) {    const temp = num2    num2 = num1    num1 = temp % num1  }
  return num2}

复制代码

解题思路：

基于以上分析，那么该题就转换成了：在nums中，是否有两个数是互质的
假设nums[1]和nums[4]互质，那么从nums[0]一直到nums[4]的所有数字，最大公约数是1
因此我们只要计算除nums[0]到nums[3]的最大公约数，与nums[4]的最大公约数为1即可
一旦nums中有两个数的最大公约数为1，那么nums中所有数字的最大公约数就是1，nums一定是个“好数组”

/** * @param {number[]} nums * @return {boolean} */var isGoodArray = function(nums) {  // 缓存依次对数组每一项求解的最大公约数  // 初始值可以是任意值，nums[0]的最大公约数就是其自身  // 最大公约数的求解会从nums[0]开始，所以无需设置初始值为nums[0]  let divisor = 0
  for (const num of nums) {    // 计算已知最大公约数和num的最大公约数    divisor = gcd(divisor, num)
    // 如果已遍历数字的最大公约数为1，那么nums的最大公约数只能是1，可提前退出    if (divisor === 1) {      break    }  }
  // 如果nums的最大公约数为1，就是一个好数组  return divisor === 1};
// 计算最大公约数(greatest common divisor)的函数const gcd = (num1, num2) => {  // 如果num2 < num1，两个数会被对调  return num1 === 0 ? num2 : gcd(num2 % num1, num1)}