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

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：

prefixGcd = [2, 6, 2]。排序后形成 [2, 2, 6]。

将最小和最大的元素配对：gcd(2, 6) = 2。剩下的中间元素 2 被忽略。因此，总和为 2。

题目来自力扣3867。

一、完整分步详细执行流程

步骤1：遍历原数组，逐位计算前缀最大值 mxi、生成 prefixGcd 数组

遍历下标从0到数组末尾，全程维护一个全局变量 mx，代表区间 nums[0] ~ nums[i] 的最大值，每轮操作逻辑：

1. 1. 读取当前下标 i 的数组元素 nums[i]；
2. 2. 对比当前 mx 和 nums[i]，更新 mx 为两者中更大的值，得到当前区间最大值 mxi；
3. 3. 计算 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，即为最终输出。

二、全局完整逻辑概括

1. 1. 一次线性扫描原数组，同步维护前缀最大值，同步生成等长 prefixGcd 数组；
2. 2. 对 prefixGcd 执行标准升序排序；
3. 3. 双指针首尾配对遍历排序后的数组，成对计算gcd并累加，中间落单元素丢弃；
4. 4. 返回累加后的总和。

三、时间复杂度分析

设数组长度为 n（1 ≤ n ≤ 1e5）

1. 1. 生成 prefixGcd：单次线性遍历 O(n)；单次gcd欧几里得算法复杂度为对数级常数，可忽略，整体这一步 O(n)。
2. 2. 排序 prefixGcd：Go标准库 slices.Sort 底层为快速排序，时间复杂度 O(n log n)，是整个算法的瓶颈。
3. 3. 首尾配对遍历：仅循环 n/2 次，线性 O(n)，单次gcd为常数级。

总时间复杂度：O(n log n)

四、额外空间复杂度分析

1. 1. 额外开辟长度为n的 prefixGcd 数组存储中间结果，占用 O(n) 空间；
2. 2. 排序的栈/临时空间为排序算法内置开销，不计入额外业务空间；
3. 3. 仅使用常数级临时变量 mx、ans、左右指针等。

总额外空间复杂度：O(n)

Go完整代码如下：

.

package main

import (
    "fmt"
    "slices"
)

func gcdSum(nums []int) (ans int64) {
    n := len(nums)
    pre := make([]int, n)
    mx := 0
    for i, x := range nums {
        mx = max(mx, x)
        pre[i] = gcd(x, mx)
    }

    slices.Sort(pre)
    for i := range n / 2 {
        ans += int64(gcd(pre[i], pre[n-1-i]))
    }
    return
}

func gcd(a, b int)int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}

func main() {
    nums := []int{2, 6, 4}
    result := gcdSum(nums)
    fmt.Println(result)
}

在这里插入图片描述

Python完整代码如下：

.

# -*-coding:utf-8-*-

import math

def gcd_sum(nums):
    n = len(nums)
    pre = []
    mx = 0
    for x in nums:
        mx = max(mx, x)
        pre.append(math.gcd(x, mx))
    
    pre.sort()
    ans = 0
    for i in range(n // 2):
        ans += math.gcd(pre[i], pre[n - 1 - i])
    return ans

if __name__ == "__main__":
    nums = [2, 6, 4]
    result = gcd_sum(nums)
    print(result)

在这里插入图片描述

C++完整代码如下：

.

#include <iostream>
#include <vector>
#include <algorithm>

// 自定义 gcd 函数（欧几里得算法）
int gcd(int a, int b) {
    while (a != 0) {
        int tmp = a;
        a = b % a;
        b = tmp;
    }
    return b;
}

long long gcdSum(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> pre(n);
    int mx = 0;
    for (int i = 0; i < n; ++i) {
        mx = std::max(mx, nums[i]);
        pre[i] = gcd(nums[i], mx);
    }

    std::sort(pre.begin(), pre.end());

    long long ans = 0;
    for (int i = 0; i < n / 2; ++i) {
        ans += gcd(pre[i], pre[n - 1 - i]);
    }
    return ans;
}

int main() {
    std::vector<int> nums = {2, 6, 4};
    long long result = gcdSum(nums);
    std::cout << result << std::endl;
    return0;
}

在这里插入图片描述

·

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。

·