Medium

题目描述

给定一个长度为 n 的整数数组 nums。

构造一个数组 prefixGcd，对于每个索引 i：

  • 设 mxi = max(nums[0], nums[1], ..., nums[i])
  • prefixGcd[i] = gcd(nums[i], mxi)

构造 prefixGcd 后：

  • 将 prefixGcd 按非递减顺序排序
  • 通过取最小的未配对元素和最大的未配对元素来形成配对
  • 重复此过程直到无法形成更多配对
  • 对于每个形成的配对，计算两个元素的最大公约数
  • 如果 n 为奇数，prefixGcd 数组中的中间元素保持未配对状态，应忽略

返回一个整数，表示所有形成配对的最大公约数值的总和。

术语 gcd(a, b) 表示 a 和 b 的最大公约数。

示例 1：

输入：nums = [2,6,4]
输出：2
解释：
构造 prefixGcd：
- i=0: nums[0]=2, mx0=2, prefixGcd[0]=gcd(2,2)=2
- i=1: nums[1]=6, mx1=6, prefixGcd[1]=gcd(6,6)=6  
- i=2: nums[2]=4, mx2=6, prefixGcd[2]=gcd(4,6)=2

prefixGcd = [2,6,2]，排序后为 [2,2,6]
配对最小和最大元素：gcd(2,6)=2，剩余中间元素 2 被忽略
因此总和为 2

示例 2：

输入：nums = [3,6,2,8]
输出：5
解释：
构造 prefixGcd：
- i=0: nums[0]=3, mx0=3, prefixGcd[0]=gcd(3,3)=3
- i=1: nums[1]=6, mx1=6, prefixGcd[1]=gcd(6,6)=6
- i=2: nums[2]=2, mx2=6, prefixGcd[2]=gcd(2,6)=2
- i=3: nums[3]=8, mx3=8, prefixGcd[3]=gcd(8,8)=8

prefixGcd = [3,6,2,8]，排序后为 [2,3,6,8]
形成配对：gcd(2,8)=2 和 gcd(3,6)=3
因此总和为 2+3=5

约束：

  • 1 <= n == nums.length <= 10^5
  • 1 <= nums[i] <= 10^9

解题思路

这道题的解题思路可以分为几个步骤：

第一步：构造 prefixGcd 数组 遍历原数组 nums，维护一个前缀最大值 mx。对于每个位置 i，计算 prefixGcd[i] = gcd(nums[i], mx)，其中 mx 是从索引 0 到 i 的最大值。

第二步：排序 将构造好的 prefixGcd 数组按非递减顺序排序。

第三步：配对计算 使用双指针技巧，左指针指向最小元素，右指针指向最大元素。每次配对计算 gcd(left_element, right_element)，然后将两个指针向中间移动。如果数组长度为奇数，中间元素会被忽略。

关键点：

  • 最大公约数的计算可以使用欧几里得算法
  • 配对策略是贪心的：总是配对当前最小和最大的元素
  • 时间复杂度主要由排序决定

这种方法的正确性在于，通过配对最小和最大元素，我们能够有效地利用数组中的所有元素（除了可能的中间元素）。

推荐解法：直接模拟法，按题目描述的步骤依次执行。

代码实现

class Solution {
public:
    long long gcdSum(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefixGcd(n);
        int mx = 0;
        
        // 构造 prefixGcd 数组
        for (int i = 0; i < n; i++) {
            mx = max(mx, nums[i]);
            prefixGcd[i] = gcd(nums[i], mx);
        }
        
        // 排序
        sort(prefixGcd.begin(), prefixGcd.end());
        
        // 配对计算 GCD 之和
        long long result = 0;
        int left = 0, right = n - 1;
        
        while (left < right) {
            result += gcd(prefixGcd[left], prefixGcd[right]);
            left++;
            right--;
        }
        
        return result;
    }
    
private:
    int gcd(int a, int b) {
        while (b) {
            a %= b;
            swap(a, b);
        }
        return a;
    }
};

class Solution:
    def gcdSum(self, nums: list[int]) -> int:
        import math
        
        n = len(nums)
        prefix_gcd = []
        mx = 0
        
        # 构造 prefixGcd 数组
        for i in range(n):
            mx = max(mx, nums[i])
            prefix_gcd.append(math.gcd(nums[i], mx))
        
        # 排序
        prefix_gcd.sort()
        
        # 配对计算 GCD 之和
        result = 0
        left, right = 0, n - 1
        
        while left < right:
            result += math.gcd(prefix_gcd[left], prefix_gcd[right])
            left += 1
            right -= 1
        
        return result

public class Solution {
    public long GcdSum(int[] nums) {
        int n = nums.Length;
        int[] prefixGcd = new int[n];
        int mx = 0;
        
        // 构造 prefixGcd 数组
        for (int i = 0; i < n; i++) {
            mx = Math.Max(mx, nums[i]);
            prefixGcd[i] = Gcd(nums[i], mx);
        }
        
        // 排序
        Array.Sort(prefixGcd);
        
        // 配对计算 GCD 之和
        long result = 0;
        int left = 0, right = n - 1;
        
        while (left < right) {
            result += Gcd(prefixGcd[left], prefixGcd[right]);
            left++;
            right--;
        }
        
        return result;
    }
    
    private int Gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

var gcdSum = function(nums) {
    const n = nums.length;
    const prefixGcd = [];
    let mx = 0;
    
    // 构造 prefixGcd 数组
    for (let i = 0; i < n; i++) {
        mx = Math.max(mx, nums[i]);
        prefixGcd.push(gcd(nums[i], mx));
    }
    
    // 排序
    prefixGcd.sort((a, b) => a - b);
    
    // 配对计算 GCD 之和
    let result = 0;
    let left = 0, right = n - 1;
    
    while (left < right) {
        result += gcd(prefixGcd[left], prefixGcd[right]);
        left++;
        right--;
    }
    
    return result;
    
    function gcd(a, b) {
        while (b !== 0) {
            [a, b] = [b, a % b];
        }
        return a;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n + n log(max(nums)))排序需要 O(n log n)，GCD 计算需要 O(log(max(nums)))
空间复杂度O(n)存储 prefixGcd 数组