2026-07-05：数对的最大公约数之和。用go语言，给定数组 nums（长度为 n）。先对每个位置 i 生成 prefixGcd[i]：令 mxi 为 nums[0..i] 中的最大值，然后 pr

2026-07-05数对的最大公约数之和。用go语言给定数组 nums长度为 n。先对每个位置 i 生成 prefixGcd[i]令 mxi 为 nums[0…i] 中的最大值然后 prefixGcd[i] 等于 nums[i] 与 mxi 的最大公约数。随后把整个 prefixGcd 按非递减顺序排序。接着从两端开始配对每次取当前最小的未配对元素与当前最大的未配对元素组成一对配对后把这两个元素移除并继续直到无法再形成更多数对如果排序后的 prefixGcd 长度为奇数正中间那个未能配对的元素保持不变并被忽略。对每个形成的数对计算它们的最大公约数并把所有这些最大公约数加总最终返回该总和。1 n nums.length 100000。1 nums[i] 1000000000。输入 nums [2,6,4]。输出 2。解释构造 prefixGcdinums[i]mxi0…i 最大值prefixGcd[i] gcd(nums[i], mxi)022216662462prefixGcd [2, 6, 2]。排序后形成 [2, 2, 6]。将最小和最大的元素配对gcd(2, 6) 2。剩下的中间元素 2 被忽略。因此总和为 2。题目来自力扣3867。一、完整分步详细执行流程步骤1遍历原数组逐位计算前缀最大值 mxi、生成 prefixGcd 数组遍历下标从0到数组末尾全程维护一个全局变量mx代表区间nums[0] ~ nums[i]的最大值每轮操作逻辑读取当前下标 i 的数组元素 nums[i]对比当前mx和 nums[i]更新mx为两者中更大的值得到当前区间最大值 mxi计算 nums[i] 与当前 mxi 的最大公约数 gcd结果存入 prefixGcd 对应下标位置。逐位演算示例i0nums[i]2初始 mx0更新 mx2计算 gcd(2,2)2 → prefixGcd[0] 2i1nums[i]662更新 mx6计算 gcd(6,6)6 → prefixGcd[1] 6i2nums[i]446mx保持6不变计算 gcd(4,6)2 → prefixGcd[2] 2本轮结束得到原始 prefixGcd 数组[2,6,2]步骤2对 prefixGcd 数组做升序排序将数组按从小到大重新排列原数组 [2,6,2] → 排序后[2,2,6]步骤3双端配对、计算每对gcd并累加总和配对规则左指针取当前最小未配对元素右指针取当前最大未配对元素两两配对数组长度为奇数时中间单独元素直接舍弃不参与计算。操作方式左指针从数组头部0开始右指针从数组尾部n-1开始循环配对每轮完成一对后左指针右移、右指针左移直到左指针 ≥ 右指针停止。本例数组长度n3左指针 l0值2右指针 r2值6组成一对计算该对gcd(2,6)2累加至总结果 ansl自增到1r自减到1此时 l ≥ r循环终止下标1的中间元素2无配对直接忽略不参与求和。步骤4返回累加总和所有配对的gcd相加结果为2即为最终输出。二、全局完整逻辑概括一次线性扫描原数组同步维护前缀最大值同步生成等长 prefixGcd 数组对 prefixGcd 执行标准升序排序双指针首尾配对遍历排序后的数组成对计算gcd并累加中间落单元素丢弃返回累加后的总和。三、时间复杂度分析设数组长度为 n1 ≤ n ≤ 1e5生成 prefixGcd单次线性遍历 O(n)单次gcd欧几里得算法复杂度为对数级常数可忽略整体这一步 O(n)。排序 prefixGcdGo标准库 slices.Sort 底层为快速排序时间复杂度 O(n log n)是整个算法的瓶颈。首尾配对遍历仅循环 n/2 次线性 O(n)单次gcd为常数级。总时间复杂度O(n log n)四、额外空间复杂度分析额外开辟长度为n的 prefixGcd 数组存储中间结果占用 O(n) 空间排序的栈/临时空间为排序算法内置开销不计入额外业务空间仅使用常数级临时变量 mx、ans、左右指针等。总额外空间复杂度O(n)Go完整代码如下packagemainimport(fmtslices)funcgcdSum(nums[]int)(ansint64){n:len(nums)pre:make([]int,n)mx:0fori,x:rangenums{mxmax(mx,x)pre[i]gcd(x,mx)}slices.Sort(pre)fori:rangen/2{ansint64(gcd(pre[i],pre[n-1-i]))}return}funcgcd(a,bint)int{fora!0{a,bb%a,a}returnb}funcmain(){nums:[]int{2,6,4}result:gcdSum(nums)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importmathdefgcd_sum(nums):nlen(nums)pre[]mx0forxinnums:mxmax(mx,x)pre.append(math.gcd(x,mx))pre.sort()ans0foriinrange(n//2):ansmath.gcd(pre[i],pre[n-1-i])returnansif__name____main__:nums[2,6,4]resultgcd_sum(nums)print(result)C完整代码如下#includeiostream#includevector#includealgorithm// 自定义 gcd 函数欧几里得算法intgcd(inta,intb){while(a!0){inttmpa;ab%a;btmp;}returnb;}longlonggcdSum(std::vectorintnums){intnnums.size();std::vectorintpre(n);intmx0;for(inti0;in;i){mxstd::max(mx,nums[i]);pre[i]gcd(nums[i],mx);}std::sort(pre.begin(),pre.end());longlongans0;for(inti0;in/2;i){ansgcd(pre[i],pre[n-1-i]);}returnans;}intmain(){std::vectorintnums{2,6,4};longlongresultgcdSum(nums);std::coutresultstd::endl;return0;}