Hard

题目描述

给定一个正整数数组 nums。你需要从数组中选择一些数字的子集，将每个数字乘以一个整数，然后将所有这些数字相加。如果你能通过任何可能的子集和乘数从数组中得到和为 1，则该数组被称为好数组。

如果数组是好数组，返回 true，否则返回 false。

示例 1：

输入：nums = [12,5,7,23]
输出：true
解释：选择数字 5 和 7。
5*3 + 7*(-2) = 1

示例 2：

输入：nums = [29,6,10]
输出：true
解释：选择数字 29、6 和 10。
29*1 + 6*(-3) + 10*(-1) = 1

示例 3：

输入：nums = [3,6]
输出：false

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 方程 ax+by=1 当且仅当 gcd(a,b) = 1 时有解
  • 可以推广这个公式，参考贝祖等式（Bézout’s lemma）

解题思路

这道题的核心是贝祖等式（Bézout’s lemma）。该等式表明：对于整数 a₁, a₂, …, aₙ，方程 a₁x₁ + a₂x₂ + … + aₙxₙ = 1 有整数解当且仅当 gcd(a₁, a₂, …, aₙ) = 1。

思路分析：

  1. 题目要求我们从数组中选择一些数字，每个数字乘以一个整数（可以是正数、负数或零），使得它们的和等于1
  2. 根据贝祖等式，这等价于求整个数组所有数字的最大公约数是否为1
  3. 如果 gcd(nums) = 1，那么存在整数系数使得线性组合等于1，答案是true
  4. 如果 gcd(nums) > 1，那么任何线性组合都是该最大公约数的倍数，不可能等于1，答案是false

算法步骤：

  • 计算数组中所有数字的最大公约数
  • 判断最大公约数是否等于1

优化技巧：

  • 可以边遍历边计算gcd，一旦发现gcd为1就可以提前返回true
  • 利用 gcd(a,b,c) = gcd(gcd(a,b),c) 的性质

代码实现

class Solution {
public:
    bool isGoodArray(vector<int>& nums) {
        int g = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            g = __gcd(g, nums[i]);
            if (g == 1) return true;
        }
        return g == 1;
    }
};

class Solution:
    def isGoodArray(self, nums: List[int]) -> bool:
        from math import gcd
        g = nums[0]
        for num in nums[1:]:
            g = gcd(g, num)
            if g == 1:
                return True
        return g == 1

public class Solution {
    public bool IsGoodArray(int[] nums) {
        int g = nums[0];
        for (int i = 1; i < nums.Length; i++) {
            g = Gcd(g, nums[i]);
            if (g == 1) return true;
        }
        return g == 1;
    }
    
    private int Gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

var isGoodArray = function(nums) {
    let gcd = nums[0];
    for (let i = 1; i < nums.length; i++) {
        gcd = getGCD(gcd, nums[i]);
        if (gcd === 1) return true;
    }
    return gcd === 1;
};

function getGCD(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n log(max(nums)))
空间复杂度O(1)

说明：

  • 时间复杂度：需要遍历数组一次，每次gcd操作的时间复杂度为O(log(min(a,b)))，最坏情况下为O(log(max(nums)))
  • 空间复杂度：只使用常数级别的额外空间