LeetCode 1250. 检查「好数组」
题目描述
题意分析
从正整数数组中选择一些元素，每个选中元素可以乘任意整数系数，再把结果相加。判断是否能恰好得到一，能则返回真，否则返回假。
系数可以为正数、负数或零，因此不是只做正数相加的子集和问题。没有选择的元素等价于系数取零，可以统一考虑整个数组的整数线性组合；只需判断存在性，不需要输出系数。
解法：最大公约数判定
核心思路
[!blue]
设全部元素的最大公约数为
g。因为g整除每个元素，也整除它们的任意整数倍及这些倍数之和，所以所有可能结果都必须是g的倍数。若能得到一，必然有g = 1，这是必要条件。反方向由裴蜀定理保证：若干整数的最大公约数本身可以表示成这些整数的整数系数之和。因此
g = 1时，一定存在题目允许的系数组合得到一，必要条件同时也是充分条件。这个结论也能从辗转相除理解：每步余数都是
a - q * b，仍然是旧参数的整数线性组合，最终得到的最大公约数可以反向表示成最初两个数的组合。再将这个公约数与下一个数求公约数，逐次代入，就能推广到整个数组，不需要某一对数先互质。代码逐个维护已经扫描元素的最大公约数。初值设为零，利用
gcd(0, x) = x统一处理首项；一旦得到一，后面继续与任何正整数求公约数都仍为一，可以直接返回。若扫描完仍大于一，全部组合都被这个公因子约束，无法得到一。
解题步骤
- 将累计最大公约数
g初始化为零。- 逐个读取数组元素，更新
g = gcd(g, num)。- 求两数公约数时反复将
(a, b)更新为(b, a % b)，直到第二项为零，返回第一项。- 累计结果为一时立即返回
true。- 全部元素处理完仍未达到一，返回
false。
代码实现
class Solution {
public boolean isGoodArray(int[] nums) {
// gcd(0,x)=x，统一处理首个元素。
int g = 0;
for (int num : nums) {
g = gcd(g, num);
// 累计最大公约数成为一后，继续加入元素也不会改变。
if (g == 1) {
return true;
}
}
return false;
}
private int gcd(int a, int b) {
while (b != 0) {
// 先保留旧参数的余数，再更新两个参数。
int remainder = a % b;
a = b;
b = remainder;
}
return a;
}
}
func isGoodArray(nums []int) bool {
// gcd(0,x)=x，统一处理首个元素。
g := 0
for _, num := range nums {
g = gcd(g, num)
// 累计最大公约数成为一后，继续加入元素也不会改变。
if g == 1 {
return true
}
}
return false
}
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
复杂度分析
- 时间复杂度：上界为 $O(n\log(C+1))$，
C为最大元素，最多进行n次辗转相除，每次最多对数级取余操作。- 空间复杂度：$O(1)$，迭代维护两个取余参数和一个累计结果，无需存储系数或子集。
关键点总结
[!green]
- 公因子整除全部线性组合，给出必须满足的条件。
- 裴蜀定理保证最大公约数本身可表示，补上存在性的反向证明。
- 允许负系数和零系数，使问题能够直接使用整数线性组合结论。
- 检查整个数组的累计公约数，不能只检查是否含一或是否存在一对互质数。
易错点总结
[!yellow]
- 把系数限制为非负数，误变成只加不减的选择问题，无法使用当前判定结论。
- 只检查数组有没有一，没有一的数组仍可能通过正负整数系数组合得到一。
- 只找一对互质元素，不同元素共同参与后，整体公约数也可能才降为一。
- 将累计公约数初始化为一，后续任何输入都会维持一，导致全部误判成功。
- 在计算余数之前覆盖旧参数，会丢失原来的
a % b，破坏辗转相除。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 365. 水壶问题 | 中等 | 两题都由最大公约数刻画可表示的整数，本题要求整数线性组合恰好得到1。 |
| 补充题 154. 最大公约数 | 简单 | 对全数组逐项求gcd，最终为1即可；无需搜索每个元素的整数系数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！