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

[chencl1986]

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

关于裴蜀定理：

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

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

1. 如果有两个数a和0，那么它们的最大公约数是a
2. 如果有两个数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

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

1. 方法一：递归

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

2. 方法二：迭代

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

  return num2
}

解题思路：

1. 基于以上分析，那么该题就转换成了：在nums中，是否有两个数是互质的
2. 假设nums[1]和nums[4]互质，那么从nums[0]一直到nums[4]的所有数字，最大公约数是1
3. 因此我们只要计算除nums[0]到nums[3]的最大公约数，与nums[4]的最大公约数为1即可
4. 一旦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)
}