力扣 2447 最大公因数等于 K 的子数组数目
题目描述
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。
子数组 是数组中一个连续的非空序列。
数组的最大公因数 是能整除数组中所有元素的最大整数。
思路分析
基于滑动窗口的思想，从数组最左边的最小连续子数组开始匹配，匹配成功一次，计数器 1，同时子数组向右扩展继续匹配下一个子数组，直到遍历整个数组结束，或者公因数小于k结束（原因是：如果公因数小于k，那继续匹配的下一个也一定小于k，此时继续循环没有意义）
公因数思路：
根据性质，a，b的最大公因数等于a，a-b的最大公因数（a>b的前提下）
步骤流程
（力扣环境下）
1.定义最大公因数函数：
如果a大于b，则将a-b的值赋给a，反之则b=b-a，循环到两者相等结束（即a-b==0），返回a或b。
2.定义i指向数组的最左边，开始遍历整个数组
每次循环：
1.定义一个target保存nums【i】的值，定义j从i位置开始遍历整个数组
j每次循环：
将target与nums【j】的最大公因数赋给target，如果target==k，怎计数器count ，同时j 扩展连续子数组（求多个值的最大公因数，可以先求两个的，再与剩下的求，以此类推），但如果target小于k，则直接跳出循环。
3.循环结束后，返回count。
代码语言：javascript复制int GCD(int a,int b)
{
while((a-b)!=0)
{
if(a>b)
{
a=a-b;
}
else
{
b=b-a;
}
}
return a;
}
int subarrayGCD(int* nums, int numsSize, int k){
int i=0;
int count=0;
for(i=0;i<numsSize;i )
{
int tar=nums[i];
for(int j=i;j<numsSize;j )
{
tar=GCD(tar,nums[j]);
if(tar==k)
{
count ;
}
else if(tar<k)//小于k直接跳出，继续没有意义
{
break;
}
}
}
return count;
}
