最大公因数等于 K 的子数组数目

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

给你一个整数数组?nums?和一个整数?k ，请你统计并返回 nums?的子数组中元素的最大公因数等于 k?的子数组数目。

子数组 是数组中一个连续的非空序列。

数组的最大公因数?是能整除数组中所有元素的最大整数。

示例 1：

输入：nums = [9,3,1,2,6,3], k = 3
输出：4
解释：nums 的子数组中，以 3 作为最大公因数的子数组如下：
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]

示例 2：

输入：nums = [4], k = 7
输出：0
解释：不存在以 7 作为最大公因数的子数组。

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i], k <= 10^9

思路分析

首先我们要先理解一下题目的意思，题目会给我们一个整数数组?nums?和一个整数?k，我们需要统计并返回?nums?的子数组中元素的最大公因数等于?k?的子数组数目。

一个序列中最大公因数等于k需要满足以下条件：

• 1、所有元素均为k的倍数；
• 2、至少一个元素与其他所有元素的最大公因数都是k。

知道了这两个条件之后我们便可以开始编写代码了：

• 1、记录每个位置前后连续元素为k的倍数的个数；

因为一个序列中最大公因数等于k时，序列中所有元素均为k的倍数，所以我们可以先统计每个位置前后连续元素为k的倍数的个数。

const q1 = new Array(nums.length).fill(0);
const q2 = new Array(nums.length).fill(0);
for(let i = 0; i < q1.length; i++){
    if(i == 0){
        if(nums[i] % k == 0) q1[i] = 1;
        if(nums[q2.length - 1] % k == 0) q2[q2.length - 1] = 1;
    }else{
        if(nums[i] % k == 0) q1[i] = q1[i-1] + 1;
        if(nums[q2.length - 1 - i] % k == 0) q2[q2.length - 1 - i] = q2[q2.length - i] + 1;
    }
}

• 2、遍历找到两个相邻元素之间的最大公因数为k的位置；

如果一个序列中有两个元素的最大公因数为k,且其他元素均可以被k整除，那么这个序列所有元素的最大公因数也为k,所以我们可以找到任意一组最大公因数为k的元素来进行计算。

for(let i = 0; i < nums.length; i++){
    if(nums[i] == k) res++;
    if(i < nums.length - 1 && gcd(nums[i],nums[i + 1]) == k){
        ……
    }
}

• 3、计算当前位置可以组成满足条件的序列数。

如果找到一组相邻的元素他们的最大公因数为k,那么从当前位置向两边延伸，找到连续为k的倍数的元素组成的序列都为满足条件的序列。

如：nums = [3,3,4,1,2],k = 1

• (1)、情况1（左边序列数 * 右边序列数 = 总序列数）

我们可以看到在下标i为1的时候，gcd(nums[i],nums[i + 1]) == k，此时从i往左看，我们可以得到两个连续元素均为k的倍数，[3,3]；从i + 1往右看，我们可以得到三个连续元素均为k的倍数，[4,1,2]。
我们只需计算两个数组的组合数即可，这里的子序列需要是连续的，所以我们可以得到的组合数应该是2 * 3 = 6;分别为：[3,4],[3,4,1],[3,4,1,2],[3,3,4],[3,3,4,1],[3,3,4,1,2];

• (2)、情况2（（左边序列数 - 上一次计算的左边序列数） * 右边序列数 = 总序列数）

第二个满足条件的下标i为2，此时从i往左看，我们可以得到两个连续元素均为k的倍数，[3,3,4]；从i + 1往右看，我们可以得到三个连续元素均为k的倍数，[1,2]。
我们只需计算两个数组的组合数即可，这里的子序列需要是连续的，所以我们可以得到的组合数应该是2 * 3 = 6;分别为：[4,1],[4,1,2],[3,4,1],[3,4,1,2],[3,3,4,1],[3,3,4,1,2]，这时我们会发现，当前得出的结果与上一次得到的结果中有重复的子序列：[3,4,1],[3,4,1,2],[3,3,4,1],[3,3,4,1,2],因为左边的序列中[3,3]在上一次计算中已经计算过了，所以我们需要将这两个减去，可以得到(3 - 2) * 2 = 2，所以当前位置可以得到新的组合数为2;

• (3)、子数组长度为1

题目中是这样定义的子数组：子数组 是数组中一个连续的非空序列。，所以在遇到nums[i] == k时，该元素可以单独成组。

let res = 0;
let flag = 0;
for(let i = 0; i < nums.length; i++){
    if(nums[i] == k) res++;
    if(i < nums.length - 1 && gcd(nums[i],nums[i + 1]) == k){
        res += (i > 0 ? (q1[i] - flag) : 1) * (q2[i + 1] || 1);
        flag = q1[i];
    }
    if(nums[i] % k !== 0) flag = 0;
}

完整AC代码如下：

AC代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
 var subarrayGCD = function(nums, k) {
    const gcd = (a, b) => {
        return a % b === 0 ? b : gcd(b, a % b);
    }
    const q1 = new Array(nums.length).fill(0);
    const q2 = new Array(nums.length).fill(0);
    for(let i = 0; i < q1.length; i++){
        if(i == 0){
            if(nums[i] % k == 0) q1[i] = 1;
            if(nums[q2.length - 1] % k == 0) q2[q2.length - 1] = 1;
        }else{
            if(nums[i] % k == 0) q1[i] = q1[i-1] + 1;
            if(nums[q2.length - 1 - i] % k == 0) q2[q2.length - 1 - i] = q2[q2.length - i] + 1;
        }
    }
    let res = 0;
    let flag = 0;
    for(let i = 0; i < nums.length; i++){
        if(nums[i] == k) res++;
        if(i < nums.length - 1 && gcd(nums[i],nums[i + 1]) == k){
            res += (i > 0 ? (q1[i] - flag) : 1) * (q2[i + 1] || 1);
            flag = q1[i];
        }
        if(nums[i] % k !== 0) flag = 0;
    }
    return res;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。