难度: Medium
给你一个整数数组 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 <= 10001 <= nums[i], k <= 109运行时间: 29 ms
内存: 16.1 MB
class Solution:
def subarrayGCD(self, nums: List[int], k: int) -> int:
ans = 0
a = []
i0 = -1
for i, x in enumerate(nums):
if x % k:
a = []
i0 = i
continue
a.append([x, i])
j = 0
for p in a:
p[0] = gcd(p[0], x)
if a[j][0] != p[0]:
j += 1
a[j] = p
else:
a[j][1] = p[1]
del a[j + 1 :]
if a[0][0] == k:
ans += a[0][1] - i0
return ans
该题解通过使用滑动窗口的方法来找出所有最大公因数为k的子数组。主要步骤如下：1. 遍历数组，用数组a来存储当前考虑的子数组的信息，其中每个元素是一个列表[p[0], p[1]]，p[0]代表当前子数组的最大公因数，p[1]代表该子数组最右边的索引。2. 如果当前元素x不能被k整除，则清空数组a，并记录当前的索引i0。3. 如果x可以被k整除，将x添加到数组a中，并更新a中每个元素的最大公因数。4. 删除数组a中不再满足条件的元素，并检查a中的第一个元素是否满足最大公因数为k的条件，如果满足，则将符合条件的子数组数目累加到结果ans中。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def subarrayGCD(self, nums: List[int], k: int) -> int:
ans = 0 # 初始化结果计数
a = [] # 存储当前考虑的子数组信息
i0 = -1 # 最近一个不可用元素的索引
for i, x in enumerate(nums):
if x % k:
a = [] # 如果x不能被k整除，重置a
i0 = i # 更新最近的不可用索引
continue
a.append([x, i]) # 将当前元素添加到a中
j = 0 # 初始化j，用于内部循环
for p in a:
p[0] = gcd(p[0], x) # 更新最大公因数
if a[j][0] != p[0]:
j += 1
a[j] = p # 更新a中的元素
else:
a[j][1] = p[1] # 更新子数组的右边界
del a[j + 1 :] # 删除不符合条件的子数组
if a[0][0] == k: # 检查当前的最大公因数
ans += a[0][1] - i0 # 累加结果
return ans # 返回结果
在算法中，如果当前元素x不能被k整除，则意味着任何包含x的子数组的最大公因数不能为k。因此，需要重置数组a来停止考虑当前正在追踪的所有子数组，并重新开始。更新索引i0为当前索引i，表示从下一个元素开始可能会出现新的符合条件的子数组，这是因为当前元素x破坏了之前任何子数组的有效性。
在算法中，数组a中的每个元素p被更新为当前考虑的元素x和p[0]（当前子数组的最大公因数）的最大公因数。通过这种方式，我们确保每次更新后，数组a中的元素仍然代表着以当前元素x为结尾的有效子数组。当更新公因数后，如果发现公因数发生变化，这意味着部分子数组可能不再有效，这时将这部分子数组移动到数组a的末尾进行处理。
在算法中，删除数组a中的元素是基于最大公因数的变化。当内部循环中，通过gcd函数更新后的最大公因数与原来不同时，这意味着该子数组的最大公因数已经不符合条件了。因此，这些不再有效的子数组被移动到数组a的末尾，并在每次内部循环结束时被删除。这样确保数组a中只保留那些最大公因数有效的子数组。
用`a[0][1] - i0`计算符合条件的子数组数量是因为a[0][1]代表数组a中第一个元素（即最大公因数为k的子数组）的最右边的索引，而i0是最近一个不包含在任何有效子数组中的元素的索引。因此，`a[0][1] - i0`计算的是从i0+1（即i0之后的第一个元素）到a[0][1]（包含）的所有可能的子数组数量，这些都是以a[0][1]为结尾且最大公因数为k的子数组。