检查好数组【LC1250】
给你一个正整数数组
nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。假如该和结果为
1，那么原数组就是一个「好数组」，则返回True；否则请返回False。
思路：根据「裴蜀定理」，如果数组中元素的最大公约数为1，那么这个数组一定是好数组
class Solution { public boolean isGoodArray(int[] nums) { int ans = nums[0]; for (int i = 1; i < nums.length; i++){ ans = gcd(ans, nums[i]); if (ans == 1) return true; } return ans == 1; } public int gcd(int x, int y){ if (y == 0){ return x; } return gcd(y, x % y); } }
复杂度分析
时间复杂度：O ( n + l o g m ) 假设数组中元素的最大值为m mm
空间复杂度：O ( 1 )
