当前位置 博文首页 > Guapifang的博客：LeetCode 1685. 有序数组中差绝对值之和--前缀
给你一个 非递减 有序整数数组 nums 。
请你建立并返回一个整数数组 result，它跟 nums 长度相同，且result[i] 等于 nums[i] 与数组中所有其他元素差的绝对值之和。
换句话说， result[i] 等于 sum(|nums[i]-nums[j]|) ，其中 0 <= j < nums.length 且 j != i （下标从 0 开始）。
示例 1：
输入：nums = [2,3,5]
输出：[4,3,5]
解释：假设数组下标从 0 开始，那么
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4，
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3，
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5。
示例 2：
输入：nums = [1,4,6,8,10]
输出：[24,15,13,15,21]
提示：
2 <= nums.length <= 105
1 <= nums[i] <= nums[i + 1] <= 104
因为是规定了数据是非递减的所以比较简单，某个元素nums[x]，定义前缀和sum[maxn]，那么该元素和后面的所有元素的绝对值差的和为：sum[n-1]-sum[x]-nums[x]*(n-1-x)。
AC代码
class Solution {
public:
int sum[100010];
vector<int>res;
vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
sum[0]=nums[0];
for(int i=1;i<nums.size();i++)
{
sum[i]=sum[i-1]+nums[i];
}
for(int i=0;i<nums.size();i++)
{
if(i==0)
res.push_back(sum[nums.size()-1]-sum[0]-nums[i]*(nums.size()-1));
else if(i==nums.size()-1)
res.push_back(nums[i]*(nums.size()-1)-sum[nums.size()-2]);
else
res.push_back(nums[i]*i-sum[i-1]+sum[nums.size()-1]-sum[i]-nums[i]*(nums.size()-i-1));
}
return res;
}
};
