算法题:快速绝对值求和

img

img


求解答
本题使用双循环暴力求解会超时,需要采用其他计算方法降低时间复杂度,以求在规定时间内完成求解。

数组从小到大排序
把第求和拆成两部分找到下标op为使得a[i]+a[op] > 1000 则 op以左a[i] + a[j]均小于1000,
求左边sum{a[i]...a[op-1]}可用前缀和简化,右边也是。
求 op 可以二分。
这样只用遍历一次数组即可。
复杂度也就是O(nlogn)