• Leetcode 3153. Sum of Digit Differences of All Pairs
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3153. Sum of Digit Differences of All Pairs

1. 解題思路

這一題的話只需要統計一下每一個位上0-9各自出現了多少次即可。

然后，對于每一位，答案就是：

$$s=\frac{\sum _{i=0}^9{n}_i(\sum _{j=0}^9{n}_j?n_i)}{2}=\frac{(\sum _{i=0}^9{n}_i{)}^2?\sum _{i=0}^9{n}_i^2}{2}$$

2. 代碼實現

給出python代碼實現如下：

class Solution:def sumDigitDifferences(self, nums: List[int]) -> int:cnt = defaultdict(lambda : defaultdict(int))for num in nums:idx = 0while num != 0:digit = num % 10cnt[idx][digit] += 1idx += 1num = num // 10ans = 0for idx in cnt:digits = cnt[idx].values()s = sum(digits)i2 = sum(x*x for x in digits)ans += (s**2 - i2) // 2return ans

提交代碼評測得到：耗時978ms，占用內存30.3MB。