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。
解释：
构造 prefixGcd：
| i | nums[i] | mxi（0…i 最大值） | prefixGcd[i] = gcd(nums[i], mxi) |
|---|---|---|---|
| 0 | 2 | 2 | 2 |
| 1 | 6 | 6 | 6 |
| 2 | 4 | 6 | 2 |
prefixGcd = [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 对应下标位置。
逐位演算示例
- i=0，nums[i]=2：
初始 mx=0，更新 mx=2；计算 gcd(2,2)=2 → prefixGcd[0] = 2 - i=1，nums[i]=6：
6>2，更新 mx=6；计算 gcd(6,6)=6 → prefixGcd[1] = 6 - i=2，nums[i]=4：
4<6，mx保持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开始，循环配对，每轮完成一对后左指针右移、右指针左移，直到左指针 ≥ 右指针停止。
本例数组长度n=3：
- 左指针 l=0（值2），右指针 r=2（值6），组成一对；
- 计算该对gcd(2,6)=2，累加至总结果 ans；
- l自增到1，r自减到1，此时 l ≥ r，循环终止；
- 下标1的中间元素2无配对，直接忽略，不参与求和。
步骤4：返回累加总和
所有配对的gcd相加结果为2，即为最终输出。
二、全局完整逻辑概括
- 一次线性扫描原数组，同步维护前缀最大值，同步生成等长 prefixGcd 数组；
- 对 prefixGcd 执行标准升序排序；
- 双指针首尾配对遍历排序后的数组，成对计算gcd并累加，中间落单元素丢弃；
- 返回累加后的总和。
三、时间复杂度分析
设数组长度为 n（1 ≤ n ≤ 1e5）
- 生成 prefixGcd：单次线性遍历 O(n)；单次gcd欧几里得算法复杂度为对数级常数，可忽略，整体这一步 O(n)。
- 排序 prefixGcd：Go标准库 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("fmt""slices")funcgcdSum(nums[]int)(ansint64){n:=len(nums)pre:=make([]int,n)mx:=0fori,x:=rangenums{mx=max(mx,x)pre[i]=gcd(x,mx)}slices.Sort(pre)fori:=rangen/2{ans+=int64(gcd(pre[i],pre[n-1-i]))}return}funcgcd(a,bint)int{fora!=0{a,b=b%a,a}returnb}funcmain(){nums:=[]int{2,6,4}result:=gcdSum(nums)fmt.Println(result)}Python完整代码如下：
# -*-coding:utf-8-*-importmathdefgcd_sum(nums):n=len(nums)pre=[]mx=0forxinnums:mx=max(mx,x)pre.append(math.gcd(x,mx))pre.sort()ans=0foriinrange(n//2):ans+=math.gcd(pre[i],pre[n-1-i])returnansif__name__=="__main__":nums=[2,6,4]result=gcd_sum(nums)print(result)C++完整代码如下：
#include<iostream>#include<vector>#include<algorithm>// 自定义 gcd 函数（欧几里得算法）intgcd(inta,intb){while(a!=0){inttmp=a;a=b%a;b=tmp;}returnb;}longlonggcdSum(std::vector<int>&nums){intn=nums.size();std::vector<int>pre(n);intmx=0;for(inti=0;i<n;++i){mx=std::max(mx,nums[i]);pre[i]=gcd(nums[i],mx);}std::sort(pre.begin(),pre.end());longlongans=0;for(inti=0;i<n/2;++i){ans+=gcd(pre[i],pre[n-1-i]);}returnans;}intmain(){std::vector<int>nums={2,6,4};longlongresult=gcdSum(nums);std::cout<<result<<std::endl;return0;}
