Sum of Absolute Differences in a Sorted Array
给一个排序好的数组, 求里面某个数字的与其他数字的绝对值之和.
这个题通过观察就可以看出来是前序和+后序和, 但是因为前序和后序是从两侧算的, 所以要通过减法使得从数字当前坐标开始计算.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution { public int[] getSumAbsoluteDifferences(int[] nums) { int n = nums.length; int[] res = new int[n]; int[] pre = new int[n + 1]; int[] sub = new int[n + 1]; for(int i = 1; i <=n; i++) { pre[i] = nums[i - 1] + pre[i - 1]; } for(int i = n - 1;i >= 0; i--) { sub[i] = nums[i] + sub[i + 1]; } for(int i = 0; i < n; i++) { res[i] = (i * nums[i] - pre[i]) + (sub[i] - nums[i] * (n - i)); } return res; } } |