C语言每日一题（20）最大公因数等于 K 的子数组数目

对编程一片赤诚的小吴

发布于 2024-01-23 15:03:35

1130

发布于 2024-01-23 15:03:35

文章被收录于专栏：热爱编程的证据热爱编程的证据

力扣 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。

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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-01-23，如有侵权请联系 cloudcommunity@tencent.com 删除

函数