千问 LeetCode 1862.向下取整数对和 public int sumOfFlooredPairs(int[] nums)
这是一道经典的算法题，考察的是前缀和与数论分块（倍数枚举）的思想。
如果直接暴力枚举每一对 (i, j)，时间复杂度是 O(N^2)，在数据量较大时会超时。我们需要转换思路：不直接计算每一对，而是计算每一个数字作为分母时，它能对总和贡献多少。
以下是完整的 Java 代码实现及详细解析：
🚀 核心思路
1. 统计频率：首先统计数组中每个数字出现的次数。
2. 前缀和预处理：计算前缀和数组，这样我们可以在 O(1) 的时间内查询任意区间 [L, R] 内有多少个数组中的元素。
3. 枚举分母与倍数：
* 遍历每一个出现过的数字 x 作为分母。
* 对于分母 x，我们枚举它的倍数 k（即商为 k）。
* 当分母为 x，商为 k 时，被除数（分子）的取值范围是 [k cdot x, (k+1) cdot x - 1]。
* 利用前缀和快速算出这个范围内有多少个数字，乘以 k（商）和 x 的出现次数，累加到答案中。
💻 Java 代码实现
import java.util.Arrays;
class Solution {
private static final int MOD = 1000000007;
public int sumOfFlooredPairs(int[] nums) {
// 1. 找到数组中的最大值，确定计数数组的大小
int maxVal = Arrays.stream(nums).max().getAsInt();
// 2. 统计每个数字出现的频率
// count[i] 表示数字 i 在 nums 中出现的次数
int[] count = new int[maxVal + 1];
for (int num : nums) {
count[num]++;
}
// 3. 计算前缀和
// prefixSum[i] 表示数值在 [0, i] 范围内的元素总个数
// 这样可以在 O(1) 时间内查询区间 [L, R] 内的元素个数
int[] prefixSum = new int[maxVal + 1];
prefixSum[0] = count[0];
for (int i = 1; i 0 ? prefixSum[lowerBound - 1] : 0);
if (countInRange > 0) {
// 贡献值 = (该范围内元素个数) * (商 k) * (分母出现的次数)
// 分母出现次数是因为数组中可能有多个相同的分母
long contribution = (long) countInRange * k * count[denominator];
ans = (ans + contribution) % MOD;
}
}
}
return (int) 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
前缀和数组 prefixSum 让我们能瞬间算出数组中有多少个元素落在 [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。
* 商为 3：分子范围 [6, 7]。无。
* 商为 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。
这个逻辑与题目示例完全吻合。