【枚举 + 求最大公约数方法】最大公约数等于K的子数组数目问题

慢一点是为了快一点，加油，大家 ，不要放弃 ! —— 2022/11/13

一、题目描述：

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。
注：子数组 是数组中一个连续的非空序列。数组的最大公因数 是能整除数组中所有元素的最大整数。

示例：

二、思路

对本题，我们可以将其分解为下列两个子问题，对每个子问题我们给出其相应的解决方法：

• 对子数组问题，我们使用双重 for 循环，枚举出每个可能产生的子数组 ，事实上，对子数组问题很多采用枚举出每个子数组，然后对每个子数组再执行判断来解决的。
• 对求最大公约数问题，我们采用欧几里得算法，也就是我们高中时候学过的辗转相除法来解决。

其递归解决的公式如下(最大公约数 Greatest Common Divisor 的缩写为GCD)：

						gcd(a, b) = gcd(b, a % b)
1

递归结束条件为： 当 b == 0 时， 得到的 a 就是最大公约数 ，以求取 6， 18 的最大公约数为例，该算法执行过程图解如下：

三、代码

根据上述分析过程，我们可以写出如下代码：

    // 以 k 为最大公约数的子树组数目（子数组是数组中一个连续的非空的元素序列） —— 子数组类型题，直接枚举 + 使用辗转相除法求最大公约数
    public int subarrayGCD(int[] nums, int k) {
        int res = 0;
        for(int i=0; i<nums.length; i++){
            int gcb = nums[i]; // 先初始化最大公约数值 gcb 为子数组第一个元素值
            for(int j=i; i<nums.length; j++){
                gcb = getGCD(gcb, nums[j]); // 更新最大公约数值
                if(gcb == k){ // 得到满足条件的子数组
                    res++;
                }
            }
        }
        return res;
    }

    public int getGCD(int a, int b){ // 求取 a, b 的最大公约数方法
        return b==0 ? a : getGCD(b, a % b);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

四、变式： 最小公倍数为 k 的子数组数目

题目描述 ：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的 子数组 中满足 元素最小公倍数为 k 的子数组数目。
注： 子数组 是数组中一个连续非空的元素序列。数组的最小公倍数 是可被所有数组元素整除的最小正整数。
示例：

思路：

解决这道题，我们只需要明确 a 和 b 的最大公约数和其最小公倍数之间的关系：

			 (a * b) / a和b的最大公约数  = a和b的最大公倍数
1

知道了上面的关键后，我们只需要对上一题求最大公约数的代码稍加改动，就可以写出本题的代码。

代码：

    // 以 k 为最小公倍数的子数组数目 （子数组是数组中一个连续的非空的元素序列）—— 利用最小公倍数与最大公约数之间的关系
    public int subarrayLCM(int[] nums, int k) {
        int res = 0;
        for(int i=0; i<nums.length; i++){
            int lcm = nums[i];
            for(int j=i; j< nums.length; j++){
                lcm = (lcm * nums[j]) / getGCD(lcm, nums[j]);
                if(lcm == k) {
                    res++;
                }
            }
        }
        return res;
    }
    
    public int getGCD(int a, int b){
        return b==0 ? a : getGCD(b, a % b);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18