思路

因为当且仅当 ai=aj，才可以将这两个数配对。
n = len(nums)
对于ai，0 <= j < n，
配对成功的条件为 MIN(ai - aj)
那么aj一定为排序后ai的前一个数或者后一个数，

假设存在a<b<c<d

只会存在两种配对情况
1. b和c配对，a和d配对，则ans1 = c - b + d - a
2. a和b配对，c和d配对，则ans2 = b - a + d - c
ans1 - ans2 = 2*(c - b) > 0
所以配对情况2优于配对情况1，可扩展到n个数上

代码

n = int(input())
nums = list(map(int, input().split()))
nums.sort()
ans = 0
for i in range(0, n, 2):
    ans += (nums[i+1] - nums[i])
print(ans)

复杂度分析

• T:O(n)
• S:O(1)