📘 題目敘述
給你一個長度為 n 的整數陣列 nums。
請先建立一個陣列 prefixGcd，對每個 index
i：
- 令
mxi = max(nums[0], nums[1], ..., nums[i]) prefixGcd[i] = gcd(nums[i], mxi)
建立完 prefixGcd 後：
- 先將
prefixGcd依非遞減順序排序 - 然後每次取目前最小的未配對元素和最大的未配對元素配成一組
- 重複這個動作，直到不能再配對為止
對每一組配對，計算這兩個數的 gcd。
如果 n 是奇數，排序後中間那個元素不會被配對，直接忽略。
請回傳所有配對的 gcd 值總和。
gcd(a, b) 表示 a 和
b 的最大公因數。
條件限制
1 <= n == nums.length <= 10^51 <= nums[i] <= 10^9
🧠 解題思路
這題照題目要求一步一步做就可以。
整體分成三段：
- 先建出
prefixGcd - 把
prefixGcd排序 - 用雙指標從最小和最大往中間配對，累加每組的
gcd
先看第一段。
題目定義：
mxi是前綴最大值prefixGcd[i] = gcd(nums[i], mxi)
所以我在掃 nums 的時候，會一路維護目前前綴最大值
mxi。
每到一個位置 i：
- 先更新
mxi = max(mxi, nums[i]) - 再算
pfg[i] = gcd(nums[i], mxi)
這樣 pfg 就是題目要的 prefixGcd。
接著第二段，把 pfg 排序。
排序之後，題目說配對方式是：
- 最小的配最大的
- 次小的配次大的
- 一直做下去
所以第三段就很自然地用雙指標：
l指向最左邊r指向最右邊
每次把：
gcd(pfg[l], pfg[r])
加進答案，然後：
l++r--
如果長度是奇數，最後中間那個元素會自己剩下來，而
while (l < r) 本來就不會去配它，所以剛好符合題意。
也就是說，這題的核心就是：
先依題意建出
prefixGcd，排序後再用雙指標從兩端往中間配對並累加每組的gcd。
所有變數
n：陣列長度pfg：題目中的prefixGcd陣列-
mxi：目前掃到位置i時，前綴nums[0...i]的最大值 ans：所有配對gcd的總和-
l：排序後pfg的左指標，指向目前最小的未配對元素 -
r：排序後pfg的右指標，指向目前最大的未配對元素
🪜 主要流程步驟
1. 先準備 prefixGcd 陣列和前綴最大值
int n = nums.size();
vector<int> pfg(n);
int mxi = INT_MIN;這裡：
n是陣列長度pfg用來存題目要的prefixGcdmxi用來記目前前綴中的最大值
一開始 mxi 先設成很小，之後每掃到一個元素就更新。
2. 掃一次 nums，依題意建出 prefixGcd
for (int i = 0; i < n; i++) {
mxi = max(mxi, nums[i]);
pfg[i] = gcd(nums[i], mxi);
}這一步是照題目定義直接做。
對每個位置 i：
-
mxi = max(mxi, nums[i])- 把目前前綴最大值更新好
-
pfg[i] = gcd(nums[i], mxi)- 這就是題目定義的
prefixGcd[i]
- 這就是題目定義的
例如如果前面最大值一路變成：
266
那對應位置就會分別去算：
gcd(nums[i], 2)gcd(nums[i], 6)gcd(nums[i], 6)
這樣整個 pfg 就建好了。
3. 把 prefixGcd 排序
sort(pfg.begin(), pfg.end());因為題目接下來要求的配對方式是：
- 最小的未配對元素
- 配最大的未配對元素
所以一定要先排序。
排序完之後，整個配對順序就很清楚了。
4. 用雙指標從最左和最右開始配對
long long ans = 0;
int l = 0, r = n - 1;
while (l < r) {
ans += gcd(pfg[l], pfg[r]);
l++;
r--;
}這一段是在做題目指定的配對方式。
l指向目前最小的未配對元素r指向目前最大的未配對元素
每次都把這兩個數配成一組，並把它們的 gcd 加到
ans 裡。
然後：
l++r--
表示這一組已經配完，改處理下一組。
如果 n 是奇數，最後會剩下一個中間元素：
- 例如
l == r
但因為迴圈條件是
while (l < r)，所以那個中間元素不會被拿去配對，剛好符合題目要求「中間元素忽略」。
5. 最後回傳答案
return ans;
當所有可以配對的元素都處理完後，ans 就是所有 formed
pairs 的 gcd 總和，直接回傳即可。
⏱️ 複雜度
設 n = nums.length。
-
時間複雜度：
O(n log n)
建立prefixGcd需要掃一次陣列，排序需要O(n log n)，最後雙指標再掃一半，整體由排序主導。 -
空間複雜度：
O(n)
額外使用了一個長度為n的pfg陣列。
💻 程式碼實作
class Solution {
public:
long long gcdSum(vector<int>& nums) {
int n = nums.size();
vector<int> pfg(n);
int mxi = INT_MIN;
for (int i = 0; i < n; i++) {
mxi = max(mxi, nums[i]);
pfg[i] = gcd(nums[i], mxi);
}
sort(pfg.begin(), pfg.end());
long long ans = 0;
int l = 0, r = n - 1;
while (l < r) {
ans += gcd(pfg[l], pfg[r]);
l++;
r--;
}
return ans;
}
};