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

2023-12-16 23:29:14

说在前面

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

题目描述

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

文章来源:https://blog.csdn.net/Twinkle_sone/article/details/135039287
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。