本文介绍一种时间复杂度为 o(n log n) 的最优算法，用于在任意长度数组中选出不相交数对，使各对绝对差之和最小；核心思想是排序后利用前缀/后缀差分预处理，避免暴力枚举，尤其显著优化奇数长度数组的计算效率。
本文介绍一种时间复杂度为 o(n log n) 的最优算法，用于在任意长度数组中选出不相交数对，使各对绝对差之和最小；核心思想是排序后利用前缀/后缀差分预处理，避免暴力枚举，尤其显著优化奇数长度数组的计算效率。
在数组中将元素两两配对（不重复、全覆盖），并计算每对元素的绝对差值之和，目标是使该总和最小。观察可知：最优配对一定发生在排序后的相邻元素之间——因为若存在交叉配对（如 a
对于偶数长度数组，直接排序后按 arr[1]−arr[0] + arr[3]−arr[2] + ... 累加即可（因已升序，绝对值可省略）。但奇数长度时需舍弃一个元素，再对剩余偶数个元素做相邻配对。暴力做法是尝试删除每个元素并重算，时间复杂度达 O(n²)，不可接受。
高效解法的关键洞察在于：删除不同位置元素所对应的配对方案，在符号分布上具有高度规律性。以排序后数组 [A, B, C, D, E, F, G]（长度 7）为例，删除第 i 个元素后，剩余元素的最优相邻配对会自然形成固定符号模式：
删 A: -B +C -D +E -F +G → sum = (C−B) + (E−D) + (G−F) 删 B: A -C +D -E +F -G → sum = (C−A) + (E−D) + (G−F) ❌ 错误？注意：实际配对应为 (A,C)? 不对！
更严谨地，我们重新审视配对逻辑：
当删除索引 k 的元素后，左侧 k 个与右侧 n−1−k 个元素需各自内部配对。由于最优配对必为相邻，且总长度为偶数，实际形成的配对结构是：
- 若
k为偶数（即左侧有偶数个），则左侧可完全配对（0–1, 2–3,…），右侧也偶数个，同样完全配对（k+1–k+2,…）； - 若
k为奇数，则左侧剩奇数个 → 最右一个无法配对，必须与右侧最左一个配对，导致“跨段” —— 这会使分析复杂化。
但原答案提示了更简洁的视角：所有合法删除方案对应的差值表达式，本质上是对排序后数组的线性组合，系数仅取 {−1, 0, +1}，且相邻方案间仅差常数项。经严格推导可得：
✅ 正确高效策略：
- 排序数组
arr； - 预处理两个数组：
-
left[i]：arr[0..i]中偶数长度前缀的最小配对和（即取arr[0..i]且i为奇数时的even_arr_sum）； -
right[j]：arr[j..n−1]中偶数长度后缀的最小配对和；
-
- 对每个可能的删除位置
k（0 ≤ k arr[k]，则剩余部分被分为arr[0..k−1]和arr[k+1..n−1]。为使总长度为偶数，这两段长度奇偶性必须相同。因此：- 当
k为偶数 → 左段长k（偶），右段长n−1−k（因n奇 ⇒n−1偶 ⇒n−1−k偶），两段均可独立最优配对； - 当
k为奇数 → 两段均为奇数长，无法独立配对 → 必须将左段末与右段首“桥接”，即用arr[k−1]与arr[k+1]配对，其余分别配对。
- 当
然而，更通用且实现简洁的方法是：利用动态规划或预处理前后缀，避免重复计算。但针对本题约束，最优实践是采用「符号累加差分法」——正如答案所提示：
对排序后数组
a[0..n−1]，定义初始删除a[0]的和为S₀ = Σ_{i=0}^{(n−3)/2} (a[2i+2] − a[2i+1])；
则删除a[k]的和Sₖ = Sₖ₋₁ − a[k−1] + a[k]（需调整索引偏移，实际需分奇偶讨论）。
但为确保正确性与可读性，推荐以下稳健 O(n log n) 实现：
def smallest_sum(arr):
arr = sorted(arr)
n = len(arr)
if n % 2 == 0:
return sum(arr[i+1] - arr[i] for i in range(0, n, 2))
# n is odd: precompute prefix and suffix even-length pair sums
# left[i] = min sum for arr[0:i] (i must be even)
left = [0] * (n + 1)
for i in range(2, n + 1, 2):
left[i] = left[i-2] + arr[i-1] - arr[i-2]
# right[i] = min sum for arr[i:n] (n-i must be even)
right = [0] * (n + 1)
for i in range(n - 2, -1, -2):
right[i] = right[i+2] + arr[i+1] - arr[i]
# Try removing each element at index k
ans = float('inf')
for k in range(n):
# After removing k, left part: [0, k), right part: [k+1, n)
left_len = k
right_len = n - 1 - k
if left_len % 2 == 0 and right_len % 2 == 0:
s = left[k] + right[k+1]
elif left_len % 2 == 1 and right_len % 2 == 1:
# bridge: pair arr[k-1] and arr[k+1], then rest
if k > 0 and k 1 else 0) + (arr[k+1] - arr[k-1]) + (right[k+2] if k+2 <p>⚠️ 注意事项： </p>
- 该算法依赖排序，故时间复杂度主导项为 O(n log n)；
- 边界情况（如
n=1或n=3）需单独验证，n=1应返回 0（无可配对），n=3时仅三种删除，可直接计算； - 实际应用中，可进一步合并奇偶逻辑，用统一 DP 状态
dp[i][p]表示前i个元素、当前未配对数为p（0 或 1）时的最小和，实现更普适的 O(n²) 解法（但本题 O(n log n) 已足够）； - 所有配对均基于排序后相邻性，切勿在未排序数组上直接应用。
综上，通过预处理前后缀配对和，我们成功将奇数长度问题的复杂度从 O(n²) 降至 O(n log n)，兼顾正确性与工程实用性。
