前缀和使用

力扣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。

思路：因为数组是有序的, 对数任意一个数nums[i],在数nums[i]左边的数比nums[i]小, 在nums[i]右边的数比nums[i]大,因此, 计算nums[i]和其他数的差绝对值之和可以分割为两部分来进行计算.首先计算前缀和数组prefixSum[], prefixSum[i]表示前i个数之和.
对于nums[i]的左半部分, nums[i]与其他数的差绝对值之和可计算为:

sumOfLeftDifferences = (i+1)*nums[i]-prefixSum[i];

对于nums[i]的右半部分, nums[i]与其他数的绝对值之和可计算为:

sumOfRightDifferences = prefixSum[nums.length-1]-prefixSum[i]-nums[i]*(nums.length-1-i);

所以, 当前nums[i]与左右其他数的绝对值之和为:

sumOfDifferences = sumOfLeftDifferences+sumOfRightDifferences;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] getSumAbsoluteDifferences(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int[] prefix = new int[n];
        // 计算前缀和
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            prefix[i] = sum;
        }
        // 计算每个数的差绝对值之和
        for (int i = 0; i < n; +ia+i) {
            int left = (i + 1) * nums[i] - prefix[i]; // 当前数与它左边的数的差之和
            int right = prefix[n - 1] - prefix[i] - nums[i] * (n - 1 - i); // 当前数与它右边的数的差之和
            ans[i] = left + right;
        }
        return ans;
    }
}

时间复杂度：O(n)

力扣340周赛6360：等值距离之和

给你一个下标从 0 开始的整数数组 nums 。现有一个长度等于 nums.length 的数组 arr 。对于满足 nums[j] == nums[i] 且 j != i 的所有 j ，arr[i] 等于所有 |i - j| 之和。如果不存在这样的 j ，则令 arr[i] 等于 0 。返回数组 arr 。

示例 1：
输入：nums = [1,3,1,1,2]
输出：[5,0,3,4,0]

示例 2：
输入：nums = [0,5,3]
输出：[0,0,0]

思路：arr[i]的值就是nums中nums[i] == nums[j] && j != i 的i - j的绝对值的和。暴力循环会超时。想同的数之间是相互影响的，把每种数出现的下标用哈希表存起来，再遍历哈希表，对每个数的出现下标进行求差的绝对值之和，就转化为上一题了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public long[] distance(int[] nums) {
        int n = nums.length;
        long[] ans = new long[n];
        Map<Integer, List<Integer>>  map = new HashMap<>(); // 存储每种数出现的下标
        for (int i = 0; i < n; ++i) {
            List<Integer> list = map.get(nums[i]);
            if (list == null) {
                list = new ArrayList<>();
            }
            list.add(i);
            map.put(nums[i], list);
        }
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            List<Integer> list = entry.getValue(); //某个数出现的下标集合(有序的)
            int len = list.size();
            int[] arr = new int[len];
            // 转化为数组，方便求前缀和
            for (int i = 0; i < list.size(); ++i) {
                arr[i] = list.get(i);
            }
            long s = 0;
            // 前缀和
            long[] prefix = new long[len];
            for (int i = 0; i < len; ++i) {
                s += arr[i];
                prefix[i] = s;
            }
            // 遍历每个下标
            for (int i = 0; i < arr.length; ++i) {
                long left = (long)(i + 1) * arr[i] - prefix[i]; // 当前下标与它左边的下标的差之和
                long right = prefix[len - 1] - prefix[i] - (long)arr[i] * (len - 1 - i); // 当前下标与它右边的下标的差之和
                ans[arr[i]] = left + right;  // arr[i]就是ans的索引
            }
        }
        return ans;
    }
}

时间复杂度：O(n)