2615. Sum of Distances
题目：
给你一个int阵列nums，找出一个与nums一样长的long阵列arr
其中arr[i] 为 |i-j| 的总和，j的条件为 nums[j]==nums[i] 且 j!=i
如果j不存在则设定arr[i]=0
思路：
也就是阵列里只有相同的数字需要计算，没有相同的数字就是设0
所以先统计每个数字在阵列里出现几次以及记录他们的index
然后再用PrefixSum的技巧计算每个index左右两侧的和
C#
public long[] Distance(int[] nums)
{
var groups = new Dictionary<int, List<int>>();
for (int i=0;i<nums.Length;i++)
{
if (groups.ContainsKey(nums[i]))
{
groups[nums[i]].Add(i);
}
else
{
groups.Add(nums[i], new List<int>{i});
}
}
var result = new long[nums.Length];
foreach (var group in groups.Values)
{
var numCount = group.Count;
if (numCount == 1)
{
continue;
}
var prefixSum = new long[numCount + 1];
for (int i=0;i<numCount;i++)
{
prefixSum[i+1] = prefixSum[i] + group[i];
}
for (int i=0;i<numCount;i++)
{
long index = group[i];
long leftSum = index * i - prefixSum[i];
long rightSum = (prefixSum[numCount] - prefixSum[i+1]) -
index * (numCount-1-i);
result[index] = leftSum + rightSum;
}
}
return result;
}
这里太久没人写，连标题都消失了
我当初从潜水到越来越常来的其中一个原因就是感觉这里有很多码农
很多人每天写这个会有种很多人一起努力的感觉
而现在可能大家都找到理想工作就不刷题了
我自己则是脚麻而且刷题实在太累，好久没写就会容易忘记
这题其实也是虽然大概知道怎么解，但也要偷看答案才能把PrefixSum最后的部分写出来= =