【Leetcode Daily】1685有序数组中差绝对值之和

发表于2025-07-18|更新于2025-07-19|力扣日常 | LeetcodeDaily

|总字数:360|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一个数组，要求返回其中每一个值与其它所有元素差值的绝对值。

思路分享

前缀和的思路，可以参考【Leetcode Daily】303区域和检索-数组不可变
从本题，可以学习到运用前缀和，简化一个数字与其左右两边数值之差值求解过程的方法。

https://leetcode.cn/problems/sum-of-absolute-differences-in-a-sorted-array/solutions/3603710/ling-shen-ke-hou-qian-zhui-he-by-zhi-ma-2zjb3/
比如说，先以 0 为初始值求前缀和，那么每个数字对应的前缀和值，就相当于其左侧数字之和。
然后以当前遍历的数字为基准，分别求左侧数字个基准值与左侧数字之和的差值；
以及所有数字之和（最右边的前缀和）减去左侧数字之和得到的右侧数字之和，再减去右侧数字个基准值得到右侧数值的差值。
将上面的左右数值差值相加，就是一个数字与其它数值的差值之和了。

代码解答（强烈建议自行解答后再看）

参考题解

class Solution:
    def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
        pre_sum = list(accumulate(nums, initial=0))
        n = len(nums)
        ans = []

        for i, x in enumerate(nums):
            left_sum = i*nums[i] - pre_sum[i]
            right_sum = pre_sum[n]-pre_sum[i] - (n-i)*nums[i]
            ans.append(left_sum + right_sum)
        
        return ans

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/2bf74580.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

Algorithm 前缀和距离和

相关推荐

【Leetcode Daily】2602使数组元素全部相等的最少操作次数

题目浅析想查看原题可以点击题目链接。简单地说，就是给两个数组，现在规定一次操作为对数组一的任意元素进行加一或者减一，对数组二的每个元素，求将数组一的全部数字经多次操作后，全部变成该元素的操作次数。思路分享有关距离和的基本思路，可以查看【Leetcode Daily】1685有序数组中差绝对值之和本题与此前的距离和模板题有一点不同，由于不确定要对哪个下标的数字做距离和，需要二分查找找到下标再开始求解，python 中可以通过 bisect 函数来快速找到下标（bisect_left 是求最左，而 bisect_right...

【Leetcode Daily】2615等值距离和

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个数组，求其中所有数值，各与其相同数值下标之差的绝对值之和。思路分享有关距离和的基本思路，可以查看【Leetcode Daily】1685有序数组中差绝对值之和本题是求下标之差，所以先要把数值分类，将各自的下标整理成各个数组，然后各数组就能计算其中元素与其它元素的距离和，从而提交答案。代码解答（强烈建议自行解答后再看）参考题解 1234567891011121314class Solution: def distance(self, nums: List[int]) -> List[int]: groups = defaultdict(list) for i, x in enumerate(nums): groups[x].append(i) ans = [0]*len(nums) for a in groups.values(): n = len(a) s =...

【Leetcode Daily】1094拼车

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个二维数组，其中的元素为长度 3 的一维数组，三个值分别是上车的人数，上车的下标，下车的下标，求整个过程中，车上的人数是否都小于 capacity。思路分享此前对于一段值的差值用前缀和处理，而前缀和的反面则是差分，求两个值的差值。所以差分记录的是值的变化，一个特点是，对于 a-b 区间的值加 10，相当于在差分数组上的 a 处加 10，b 处减 10. https://leetcode.cn/problems/car-pooling/solutions/2550264/suan-fa-xiao-ke-tang-chai-fen-shu-zu-fu-9d4ra/ 所以本题只要先求出整个数组的差分，再对差分做前缀和，过程中判断是否有值超过阈值即可。代码解答（强烈建议自行解答后再看）参考题解 12345678class Solution: def carPooling(self, trips: List[List[int]], capacity: int) -> bool: ...

【Leetcode Daily】1109航班预订统计

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个航班预定表，内容分别是起始航班下标，终止航班下标，预订座位数组成的多个数据，求最终每个航班预定的座位数。思路分享越是做差分的题，越是发现，差分十分擅长处理增减的累计。拿此题来讲，只要通过差分记录各个航班的累计座位数，然后求前缀和即可。 https://leetcode.cn/problems/corporate-flight-bookings/solutions/968214/hang-ban-yu-ding-tong-ji-by-leetcode-sol-5pv8/ 代码解答（强烈建议自行解答后再看）参考题解 1234567class Solution: def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]: rec = [0]*(n+2) for start, last, seats in bookings: rec[start] +=...

【Leetcode Daily】1314矩阵区域和

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个二维数组和一个数字 k，现在对于二维数组上的每个值，请求其为中心向周围延伸 k 个格子的正方形的区域和。思路分享本质上就是变形了的二维前缀和，只不过这次边界的需要自己计算和规范化，比如下面参考题解中写的 max，min 就是如此，对于超过了数组的值，尽量大或者尽量小就行。重点还是在于自己分辨清楚，边界的下标是否需要加一，由于初始化的矩阵左上多垫了一行和一列，所以计算右下坐标时也需要加一，而左上角本来需要减一，现在就不用变了。 https://leetcode.cn/problems/matrix-block-sum/solutions/101300/ju-zhen-qu-yu-he-by-leetcode-solution/ 代码解答（强烈建议自行解答后再看）参考题解 123456789101112class Solution: def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]: ...

【Leetcode Daily】1524和为奇数的子数组数目

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个整数数组，要求这个数组中所有子数组中和为奇数的数目。思路分享前缀和的思路，可以参考【Leetcode Daily】303区域和检索-数组不可变虽然是陆爻齐自己思考了出来，但如果没有提前知道是前缀和区域，应该是做不出来的。回忆解题的过程，就是思考如何快速判定奇数区域时，对做了前缀和了数组观察偶然发现，只要记录此前的奇数和偶数的数目，就能方便地计算现有的数字与此前数字之前区域的和为奇数的数目。代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415class Solution: def numOfSubarrays(self, arr: List[int]) -> int: s = list(accumulate(arr, initial=0)) even_num = 0 odd_num = 0 ans = 0 for i in s: if i%2 == 0: ...

数据加载中