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

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

说在前面

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

题目描述

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

目录
相关文章
|
网络协议 Shell 网络安全
在外SSH远程连接macOS服务器【cpolar内网穿透】
macOS系统自带有Secure Shell 客户端,它可让您登录到侦听传入SSH连接的远程服务器和台式机。我们可以用ssh username@ip来ssh到服务器,但通常局限于局域网内的远程。
1200 0
|
5月前
|
人工智能 IDE API
OpenCode 是什么?——终端里的开源 AI 编程 Agent 完全解读
2026年,Anthropic封禁第三方调用Claude Code,引爆开发者对“供应商锁定”的焦虑。开源工具OpenCode应运而生——MIT协议、终端原生、支持75+模型,首创Plan/Build双模式,将模型选择权、成本控制权与数据主权彻底交还开发者。
|
4月前
|
存储 人工智能 Apache
从向量存储到 Agentic 数据基础设施:Paimon × Milvus 如何构建 AI 原生多模态数据湖
本文整理自李钰在 Apache Flink Forward Asia 2026 的演讲,讨论 AI 与 Agent 进入生产环境后,数据湖与向量数据库“双系统”架构暴露出的结构性问题,以及 Apache Paimon 与 Milvus 围绕同一份湖数据协同的技术路径。
从向量存储到 Agentic 数据基础设施:Paimon × Milvus 如何构建 AI 原生多模态数据湖
|
4月前
|
存储 人工智能 缓存
企业AI私有化与云端协同方案:GLM5.2部署+OpenClaw/Hermes运维教程
GLM 5.2是一款753B混合专家架构开源旗舰大模型,原生支持百万Token超长上下文、复杂代码工程、长周期自主智能体任务,完整支持本地、私有云自托管部署。自托管模式能够实现全部业务数据不出环境、企业自定义推理调度、全链路操作私有化审计,对数据安全管控有严格要求的研发、金融、政企团队具备不可替代价值。整套落地链路包含硬件分级选型、多量化权重存储配置、vLLM/SGLang双推理框架部署、长期使用成本盈亏测算四大核心模块,同时可搭配轻量应用服务器部署OpenClaw、Hermes两类主流AI智能体,结合百炼Token Plan云端订阅算力构建混合AI架构,兼顾私有化数据安全与云端灵活弹性
578 1
|
5月前
|
人工智能 运维 安全
光聪明还不够,Agent “真干活”还缺一套趁手的工具
搭一个会聊天的 Agent 不难,难的是让它跑进真实业务。AgentRun 把 Skill 和 MCP 统一管理为可复用资产:Skill 规定“怎么做”,MCP 提供“能调用什么”。从工具安装、Agent 绑定到调试面板验证链路,一条路径打通 Agent 从对话入口到业务执行入口的落地。
|
4月前
|
人工智能 运维 NoSQL
OpenSpec 三阶段工作流实操:从 Propose 到 Archive让代码返工率降到三分之一以下
OpenSpec是AI原生规范驱动开发(SDD)框架,以Propose→Apply→Archive三阶段强制工作流,将需求精准转为AI可读、可验、可追溯的结构化规范,实测降低代码返工率超2/3。
614 0
|
5月前
|
SQL 存储 关系型数据库
覆盖索引:让你的查询直接从索引返回,彻底告别回表
覆盖索引是SQL优化中性价比较高的技巧,让查询直接从索引返回所需列,避免回表操作。本文解释覆盖索引的原理,通过EXPLAIN的“Using index”判断是否生效。结合复合索引设计、深分页优化(延迟关联)等场景,给出覆盖索引的使用方法和注意事项。用好覆盖索引,不改SQL逻辑,仅调整索引设计即可显著提升查询性能。
|
5月前
|
前端开发 小程序 定位技术
跑腿配送系统搭建如何对接地图导航与第三方配送
本文详解跑腿配送系统搭建核心:地图导航(定位、路径规划、轨迹展示)与第三方配送对接(订单推送、状态同步、WebSocket实时通知),涵盖高德/腾讯/百度地图选型、距离计算、智能派单、多端统一架构等实战方案,助企业高效构建本地生活配送能力。(239字)
|
5月前
|
存储 人工智能 安全
OpenHuman:本地优先的开源Agent
OpenHuman 展示了一条本地优先的 Agent 路线:把个人记忆、数据连接、自动更新结合,让 Agent 更懂你,也更尊重数据边界。
652 1
|
6月前
|
人工智能 前端开发 关系型数据库
AI 面试问答系统:一键生成专属面试题,智能评分助你拿 Offer
AI面试问答系统是一款开源智能面试备战工具:上传简历+岗位JD,AI自动生成四维面试题、追问及答案;支持背诵默写智能评分(0-100)、技能掌握度追踪(1-5星)与答案优化。兼容通义千问/GPT/DeepSeek等多模型,本地一键部署,免费开源!