LeetCode-1250. 检查「好数组」【数论，裴蜀定理】

题目描述：

给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。

假如该和结果为 1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
https://leetcode.cn/problems/check-if-it-is-a-good-array/description/

解题思路一：裴蜀定理是：ax+by=1。其中a,b是数组中的数，x,y是任意整数。如果a,b互质那么一定有解。问题即转换为寻找互质的数。

class Solution {
public:bool isGoodArray(vector<int>& nums) {int s=0;for (int x : nums) {s=gcd(x,s);if(s==1) return true;//剪枝}return s==1;}int gcd(int a, int b) {//辗转相除法if(b==0) return a;return gcd(b,a%b);}
};

时间复杂度：O(n)
空间复杂度：O(1)

解题思路二：简化代码1

class Solution {
public:bool isGoodArray(vector<int>& nums) {int s=0;for (int x : nums) {s=gcd(x,s);if(s==1) return true;//剪枝}return s==1;}
};

时间复杂度：O(n)
空间复杂度：O(1)

解题思路三：三行代码！

class Solution {
public:bool isGoodArray(vector<int>& nums) {int s=0;for (int x : nums) s=gcd(x,s);return s==1;}
};

时间复杂度：O(n)
空间复杂度：O(1)