说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。
题目描述
给你一个整数数组 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，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『
前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。
