千问 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, (k1) 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 的结果是分段的。例如 x2* 分子在 [0, 1]结果为 0* 分子在 [2, 3]结果为 1* 分子在 [4, 5]结果为 2* ...* 分子在 [2k, 2k1]结果为 k前缀和数组 prefixSum 让我们能瞬间算出数组中有多少个元素落在 [2k, 2k1] 这个区间内而不需要遍历整个数组。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 的总贡献1247。* 当分母为 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。这个逻辑与题目示例完全吻合。