题目描述
给你一个正整数数组 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
题解
这题名义上是困难难度，实际上只要知道一些数学知识，就非常的简单。
首先题目中要求挑选出一些数，然后给每个数分配整数系数，加权求和等于 1 。仔细想一想就不对劲，全选不是一样嘛？有些数系数分配 0 就行了。
假设系数分别是 ，那么问题就变成了求解下面的多元一次方程有整数解的条件：
如果你数学基础不错的话，一眼就会发现条件就是所有非零数的最大公约数为 1 ：
证明参见 n 个数的裴蜀定理[1]
代码
class Solution { public: bool isGoodArray(vector<int>& nums) { int x = nums[0], n = nums.size(); for (int i = 1; i < n; ++i) { if (nums[i]) x = gcd(x, nums[i]); } return x == 1; } int gcd(int x, int y) { return x%y ? gcd(y, x%y) : y; } };
后记
最后不管是用时还是空间消耗都超越了100%的用户。
参考资料
[1]
维基百科：裴蜀定理: https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity,
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
