题目大意：
检查「好数组」
给你一个正整数数组 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^51 <= nums[i] <= 10^9
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1250
解题思路分析：
这道题开始没有想到解题思路，看了答案之后才恍然大悟。简单来说，核心思想是找到一组数字，如果他们的最大公约数为1，那么代表结果为true，反之为false。简单来做下证明：
证明：gcd方法代表求一组数的最大公约数，如果 gcd(x1, x2, x3,…)=t>1，则 a⋅x1+b⋅x2+c⋅x3+…必定是t的倍数，所以不可能找到一组系数使其和等于1。
对于数学类的问题，必须从数学角度去思考，除此之外并没有太好的解题方法。对于本题，能够在编程上学习到的点是如何求2个数的最大公约数，简单粗暴的方式是从较小数字到1之间逐个循环，看看当前数字是否能2个数整除，找到一个最大的即使最大公约数。不过这种方式显然效率不高，我们可以通过余数法来求解。对于两个整数x和y，我们先保证x大于等于y，接下来计算出x % y的（余数）值，再与y作为参数递归本方法，直到较小的数字y等于0时，x即为两数的最大公约数。
int gcd(int x, int y) { // 求最大公约数
if(x < y) return gcd(y, x); // 保证x大于等于y
if(y == 0) return x; // 当y为0时，x即为两数的最大公约数
return gcd(y, x % y); // 否则继续递归
} 这是比较典型的算法，应该牢记下来，Leetcode之前的很多题目都用到过这一方法。
那么接下来，本题该如何求解？毕竟题目给出的子序列长度不一定为2，也就是说我们需要找到多个数的最大公约数。这其实也不难，我们可以从数组第一位开始向后循环，先计算出前两数字的最大公约数，然后在利用这个最大公约数与第3个数求最大公约数，直到所有数字循环结束，期间只要出现结果为1 的最大公约数，可直接返回true，如果直到循环结束仍未找到，返回false。
这里可能会有一个疑问，只从头到尾循环一次数组，能排查出所有的组合情况吗？答案是肯定的，举个例子，比如数组：
[2,4,7]
很明显看出2和4的最大公约数为2，4和7则为1，我们遍历一次数组并没有遍历过4和7这两个数的区间[1,2]，但是我们利用了2和4的最大公约数去和7求解，实际上是遍历了，2和7以及4和7两种情况。
看下实现代码：
public boolean isGoodArray(int[] nums) {
int x = nums[0];
for(int y : nums){
x = gcd(x, y); // 两两计算最大公约数
// 最大公约数为1，返回true
if(x==1) return true;
}
return false;
}
int gcd(int x, int y) { // 求最大公约数
if(x < y) return gcd(y, x); // 保证x大于等于y
if(y == 0) return x; // 当y为0时，x即为两数的最大公约数
return gcd(y, x % y); // 否则继续递归
} 本题解法执行时间为3ms。
Runtime: 3 ms, faster than 78.34% of Java online submissions for Check If It Is a Good Array.
Memory Usage: 51.1 MB, less than 100.00% of Java online submissions for Check If It Is a Good Array.Next challenges:
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1250-check-if-it-is-a-good-array-解题思路分析/