LeetCode 1250. 检查「好数组」

约 5 分钟
文章信息 6 个分类 7 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节跳动
标签
数组 数学 数论 最大公约数 欧几里得算法 扩展欧几里得算法 裴蜀定理
目录

题目描述

✅ 1250. 检查「好数组」

题意分析

给一个正整数数组，问能否从中选出一个非空子集，给每个选中的数配一个任意整数系数（可以是负数、可以是 0，也可以很大），使得加权和恰好等于 1。

「系数任意整数」是全部题眼。它把问题从「能不能凑出 1」这种背包式的组合搜索，变成了一个纯粹的代数问题——因为系数无界且允许负数，可选的加权和构成的不是有限集合，而是一个由这些数生成的结构。

「子集」这个词看似增加了自由度，其实是冗余的：没被选中的数完全可以配系数 0，效果一样。所以实际上可以认为所有数都参与，只是有些系数为 0。这个化简很重要，它让答案只与整个数组有关，而与「选哪些」无关。

数据规模：数组长度上限 $10^5$，元素值上限 $10^9$。这个规模明确排除任何枚举子集的做法，指向一趟线性扫描 + 每步 $O(\log C)$ 的运算。

边界：数组只有一个元素（此时答案就是这个元素是否为 1）、数组中含 1、所有元素相同、所有元素都是偶数。

解法：最大公约数判定

核心思路

裴蜀定理指出：若一组整数的最大公约数为 g，那么它们所有整数系数线性组合，恰好是 g 的整数倍。因此，能够组合出 1 的充要条件就是全数组最大公约数等于 1。

题目虽然写“选择子集”，但未选择的数等价于系数取 0，所以检查全集不会改变可行性。反过来，如果某个子集的最大公约数已经是 1，把其他数并入后，全数组最大公约数仍然只能是 1。

从左到右归并最大公约数。不变量：处理完前 i 个数后，g 等于这 i 个数的最大公约数。 初始 g = 0，利用 gcd(0, x) = x 统一处理第一个元素；归并一步后，由最大公约数的结合律，不变量继续成立。

正确性说明：若最终 g = 1，裴蜀定理保证存在一组整数系数使线性组合为 1；若 g > 1，任何线性组合都能被 g 整除，不可能等于 1。扫描中一旦得到 1，后续归并也不可能改变它，可以立即返回。

解题步骤

  1. 初始化累计最大公约数 g = 0。
  2. 依次计算 g = gcd(g, nums[i])。
  3. 若 g == 1，立即返回 true。
  4. 扫描结束仍未得到 1，则返回 false。

例如 [12, 5, 7, 23]：gcd(0,12)=12，继续归并 5 后得到 1，答案为 true；确实有 12*(-2)+5*5=1。

反例 [3,6] 的累计最大公约数为 3，所有整数线性组合都是 3 的倍数，所以答案为 false。单元素 [1] 返回 true，而 [4] 返回 false。

代码实现

class Solution {
    public boolean isGoodArray(int[] nums) {
        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 {
	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
}

复杂度分析

设数组长度为 n，最大元素为 C。

  • 时间复杂度： $O(n \log C)$。每个元素参与一次辗转相除。
  • 空间复杂度： $O(1)$。

关键点总结

  • 任意整数系数线性组合是裴蜀定理的直接信号，判据是全体数的最大公约数是否为 1。
  • “选择子集”不需要枚举：未选择元素可视为系数为 0。
  • g 始终是已扫描前缀的最大公约数，这是归并过程的核心不变量。
  • gcd(0,x)=x 消除了首元素特判；累计值变成 1 后可以安全提前结束。

易错点总结

  • 只检查数组里是否有 1： [12,5] 没有 1，但最大公约数为 1，答案仍是 true。
  • 只寻找一对互质数： [6,10,15] 中任意两数都不互质，但三个数的最大公约数是 1。
  • 把累计值初始化为 1： gcd(1,x) 恒为 1，会把 [3,6] 错判为好数组。
  • 辗转相除时先覆盖 a： 必须先保存 a % b；否则 gcd(12,5) 可能错误返回 5。
  • 改用乘积或最小公倍数： 元素可达 $10^9$，乘法容易溢出，而且与题目的充要条件无关。

相似题目

题目 难度 考察点
1071. 字符串的最大公因子 简单 把 gcd 从整数搬到字符串长度上，还需先验证拼接可交换
365. 水壶问题 中等 同样由裴蜀定理判可行，但目标值不是 1 而要判整除关系
204. 计数质数 中等 换成筛法预处理，考察的是整除关系的批量枚举而非归并
878. 第 N 个神奇数字 困难 用 lcm 做容斥后二分答案，是 gcd 的对偶量在计数中的应用