难度: Easy
给你一个数字数组 arr 。
如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。
如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。
示例 1：
输入：arr = [3,5,1] 输出：true 解释：对数组重新排序得到 [1,3,5] 或者 [5,3,1] ，任意相邻两项的差分别为 2 或 -2 ，可以形成等差数列。
示例 2：
输入：arr = [1,2,4] 输出：false 解释：无法通过重新排序得到等差数列。
提示：
2 <= arr.length <= 1000-10^6 <= arr[i] <= 10^6运行时间: 19 ms
内存: 16.0 MB
class Solution:
def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
arr.sort()
d = arr[1] - arr[0]
for i in range(1, len(arr) - 1):
if arr[i] *2 != arr[i - 1] + arr[i + 1]:
return False
return True
首先对数组进行排序，以确保数字按升序排列。接着，计算第一对相邻元素的差值，作为等差数列的公差。然后，遍历数组中的每一对相邻元素，检查它们的差值是否等于公差。如果所有相邻元素的差值都等于公差，那么数组可以形成等差数列，返回 true。否则，返回 false。
时间复杂度: O(n log n)
空间复杂度: O(1)
class Solution:
def canMakeArithmeticProgression(self, arr: List[int]) -> bool:
arr.sort() # 对数组进行排序
d = arr[1] - arr[0] # 计算公差
for i in range(1, len(arr) - 1):
if arr[i] * 2 != arr[i - 1] + arr[i + 1]: # 检查是否每一对相邻元素的差值都等于公差
return False
return True # 如果所有相邻元素的差值都等于公差，返回 true
在等差数列中，每两个相邻的元素都应满足等差关系，即相邻元素的差为一个常数（公差）。当数组经过排序后，若数组是等差数列，则必定满足任意三个连续元素a, b, c中b应等于a和c的算术中值。换句话说，2倍的b应等于a加上c。因此，`arr[i] * 2 != arr[i - 1] + arr[i + 1]`这个条件用于检查数组中任意连续三个元素是否符合这一等差关系。如果某一组不符合，说明数组不能形成等差数列。
对数组进行排序是基于等差数列的定义：等差数列的元素间隔须在逻辑上（即数值大小上）是连续的。在未排序的数组中，元素的物理位置（即数组中的位置）可能不反映真实的逻辑顺序。通过排序，我们可以确保任何相邻的两个元素在数值上是连续的，这样才能正确地验证它们之间是否存在固定的差（即公差）。未排序的数组可能会错误地判断非等差数列为等差数列，例如[4, 1, 2]在未排序前会错误地认为不是等差数列。
存在不需要排序的方法来判断等差数列。一种方法是通过计算数组中的最大值和最小值，然后使用这两个值来确定理论上的公差（(最大值-最小值)/(元素个数-1)）。接着，可以使用一个HashSet来检查每个理论上应存在的值是否都在数组中。这种方法避免了排序，但需要额外的空间来存储HashSet，并且在处理包含重复元素或计算公差时可能因为整数除法而产生误差。
在等差数列的定义中，如果存在重复元素，那么这些元素应当处于数列的连续位置。在处理重复元素时，排序后的数组将自然地将重复的元素放在一起，这不会影响等差数列的判断，因为在检查公差一致性时，连续相同的元素（重复元素）的差值为0，如果其他相邻元素的差值也为0，则它们仍然符合等差数列的条件。因此，如果所有的差值（包括重复元素造成的0差值）都一致，数组就可以形成等差数列。