周赛遇到了一道数组中所有 pair 的绝对值求和的问题 2731. Movement of Robots，直觉上 O(N^2) 的方式会 TLE，后来转换思路，发现有序数组用 O(N) 就可以做到了。
直觉上的做法，是在模拟 abs 运算：
1for i in range(N):
2 for j in range(i + 1, N):
3 res += abs(nums[i] - nums[j])
通过归纳这个过程，可以发现：
1N1 - N0, N2 - N0, N3 - N0, N4 - N0
2 N2 - N1, N3 - N1, N4 - N1
3 N3 - N2, N4 - N2
4 N4 - N3
对于 index i，
在 - 号左边会出现 i 次，因为有 i 个数比它小；在 - 号右边会出现 N - 1 - i 次，因为有 N - 1 - i 个数比它大。
那么我们可以直接用乘法计算了：
1sum(
2 nums[i] * (i - (N - 1 - i))
3 for i in range(N)
4)
那么为什么只有对有序数组才能得到这样的 O(N) 优化呢？
因为要求的是 abs，如果出现了逆序我们不知道某一步应该是 Ni - Nj 还是 Nj - Ni，会导致计数错误。