千问 LeetCode 1862题的Python代码怎么写？

这是 LeetCode 1862 题“向下取整数对和”的 Python 代码实现。

这道题如果直接双重循环暴力求解会超时，因此我们采用“前缀和 + 倍数枚举”的策略，将时间复杂度优化到 O(M log M)，其中 M 是数组中的最大值。

🐍 Python 代码实现

class Solution:
def sumOfFlooredPairs(self, nums: List[int]) -> int:
MOD = 10**9 + 7

# 1. 找到数组中的最大值，确定计数数组的大小
max_val = max(nums)

# 2. 统计每个数字出现的频率
# count[i] 表示数字 i 在 nums 中出现的次数
count = [0] * (max_val + 1)
for num in nums:
count[num] += 1

# 3. 计算前缀和
# prefix_sum[i] 表示数值在 [0, i] 范围内的元素总个数
# 这样可以在 O(1) 时间内查询任意区间 [L, R] 内的元素个数
prefix_sum = [0] * (max_val + 1)
prefix_sum[0] = count[0]
for i in range(1, max_val + 1):
prefix_sum[i] = prefix_sum[i - 1] + count[i]

ans = 0

# 4. 遍历每一个可能的数字作为分母
for denominator in range(1, max_val + 1):
# 如果该数字不存在于数组中，跳过
if count[denominator] == 0:
continue

# 5. 枚举商（倍数）
# 我们固定分母为 denominator，枚举商 k
# 此时分子 numerator 的范围是 [k * denominator, (k + 1) * denominator - 1]
# 只要 k * denominator 0 else 0)

if count_in_range > 0:
# 贡献值 = (该范围内元素个数) * (商 k) * (分母出现的次数)
# 分母出现次数是因为数组中可能有多个相同的分母
contribution = count_in_range * k * count[denominator]
ans = (ans + contribution) % MOD

k += 1

return ans

🧠 算法核心逻辑解析

1. 为什么使用前缀和？
题目要求计算 sum lfloor frac{nums[i]}{nums[j]} rfloor。
如果我们固定分母 nums[j] = x，那么对于不同的分子 nums[i]，lfloor frac{nums[i]}{x} rfloor 的结果是分段的。
例如 x=2：
* 分子在 [0, 1]，结果为 0
* 分子在 [2, 3]，结果为 1
* 分子在 [4, 5]，结果为 2
* ...
* 分子在 [2k, 2k+1]，结果为 k

前缀和数组 prefix_sum 让我们能瞬间算出数组中有多少个元素落在 [2k, 2k+1] 这个区间内，而不需要遍历整个数组。

2. 复杂度分析
* 时间复杂度：O(M log M)，其中 M 是数组中的最大值。
* 外层循环遍历分母，最多 M 次。
* 内层循环枚举倍数（商），对于分母 x，循环次数约为 M/x。
* 总次数约为 M/1 + M/2 + M/3 + ... + M/M = M times (1 + 1/2 + ... + 1/M) approx M ln M。
* 空间复杂度：O(M)，用于存储频率数组和前缀和数组。

3. 举例说明
假设 nums = [2, 5, 9]：
* 频率：count[2]=1, count[5]=1, count[9]=1。
* 当分母为 2 时 (count[2]=1)：
* 商为 1：分子范围 [2, 3]。数组中有 1 个 (即2)。贡献 1 times 1 times 1 = 1。
* 商为 2：分子范围 [4, 5]。数组中有 1 个 (即5)。贡献 1 times 2 times 1 = 2。
* 商为 4：分子范围 [8, 9]。数组中有 1 个 (即9)。贡献 1 times 4 times 1 = 4。
* 分母为 2 的总贡献：1+2+4=7。
* 当分母为 5 时：
* 商为 1：分子范围 [5, 9]。有 2 个 (5, 9)。贡献 2 times 1 times 1 = 2。
* 当分母为 9 时：
* 商为 1：分子范围 [9, 17]。有 1 个 (9)。贡献 1 times 1 times 1 = 1。
* 总和：7 + 2 + 1 = 10。

这个逻辑与题目示例完全吻合。