检查「好数组」Java

文章发布较早，内容可能过时，阅读注意甄别。

categories:

algorithm
leetcode tags:
Java author: name: JavaInterview.cn link: https://JavaInterview.cn titleTag: Java feed: enable: true description: 1250. 检查「好数组」

# 题目

给你一个正整数数组 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

# 思路

递归

# 解法

class Solution {
    public boolean isGoodArray(int[] nums) {
        int res = nums[0];
        for (int num : nums) {
            res = gcd(res, num);
            if (res == 1) break;
        }
        return res == 1; 
    }

    private int gcd(int a, int b) {
        if (b == 0) return a;
        if (b > a) return gcd(b, a);
        return gcd(b, a % b);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 总结

分析出几种情况，然后分别对各个情况实现