📘 題目敘述
如果一個數列中，任何兩個相鄰元素的差都相同，那這個數列就稱為等差數列（arithmetic progression）。
給你一個數字陣列 arr，如果 arr 可以重新排列後形成等差數列，回傳 true；否則回傳 false。
條件限制
2 <= arr.length <= 1000-10^6 <= arr[i] <= 10^6
🧠 解題思路
這題的核心是：等差數列只要「排好順序」後，相鄰差值都一樣就成立。
所以我的做法很直接：
先把 arr 排序。
排序後如果它能形成等差數列，那相鄰兩項的差一定都會等於同一個 d。
我用第一段差 arr[1] - arr[0] 當作目標差值 d，接著一路檢查每一段相鄰差是否都等於 d。只要遇到一段不等，就代表不可能形成等差數列。
所有變數
d：排序後的目標公差，設定為arr[1] - arr[0]n：陣列長度arr.size()
🪜 主要流程步驟
1. 先排序，讓數列變成「固定順序」方便檢查
我先做 sort(arr.begin(), arr.end())。
因為只要存在某種排列能形成等差數列，那把它從小到大排好後，相鄰差值也會固定一致。
2. 用第一段差值當作公差 d
排序後設定：
d = arr[1] - arr[0]
這個 d 就是我希望整個數列每一段相鄰差都一樣的目標。
3. 逐段檢查每一個相鄰差值
從 i = 1 一路檢查到 n - 2：
如果 arr[i + 1] - arr[i] != d
就直接回傳 false，因為已經破壞等差的條件。
4. 全部都符合就回傳 true
如果整個迴圈都沒出現不一致，代表每段相鄰差值都相同，所以回傳 true。
⏱️ 複雜度
- 時間複雜度：
O(n log n)（排序） - 空間複雜度：
O(1)（不計排序的額外空間；或視實作可能為O(log n)）
💻 程式碼實作
class Solution {
public:
bool canMakeArithmeticProgression(vector<int>& arr) {
sort(arr.begin(), arr.end());
int d = arr[1] - arr[0];
int n = arr.size();
for (int i = 1; i < n - 1; i++) {
if (arr[i + 1] - arr[i] != d) {
return false;
}
}
return true;
}
};
🔗 題目連結
https://leetcode.com/problems/can-make-arithmetic-progression-from-sequence/