我来搜索 LeetCode 3017 这道题的详细信息和题解。LeetCode 3017. 按距离统计房屋对数目 II题目描述给定 n 个房屋编号从 1 到 n排成一条直线。在房屋 x 和 y 之间有一条额外的街道连接。对于每个 k1 k n返回距离恰好为 k 的有序房屋对 (house1, house2) 的数量。约束条件 2 n 10^51 x, y n---核心思路这道题的关键在于将图结构分解为几个部分分别计算避免 O(n^2) 的暴力枚举。图的结构可以看作- 环Ring由 x 到 y 及连接它们的额外边形成的环长度为 ringLen y - x 1- 左链Left Line[1, x) 部分长度为 leftLineLen x - 1- 右链Right Line(y, n] 部分长度为 rightLineLen n - y需要分类讨论以下 6 种房屋对位置关系分别计算贡献 情况 描述1. bothInRing 两个房屋都在环内2. bothInTheSameLine 两个房屋都在左链或都在右链3. lineToRing 一个房屋在左链/右链另一个在环内4. lineToLine 一个房屋在左链另一个在右链最后将各情况结果相加并乘以 2因为是有序对。---Java 实现javaclass Solution {public long[] countOfPairs(int n, int x, int y) {// 确保 x yif (x y) {int temp x;x y;y temp;}final int ringLen y - x 1; // 环的长度final int leftLineLen x - 1; // 左链长度final int rightLineLen n - y; // 右链长度long[] ans new long[n];// 分别计算6种情况的贡献ans addVectors(ans, bothInRing(n, ringLen));ans addVectors(ans, bothInTheSameLine(n, leftLineLen));ans addVectors(ans, bothInTheSameLine(n, rightLineLen));ans addVectors(ans, lineToRing(n, leftLineLen, ringLen));ans addVectors(ans, lineToRing(n, rightLineLen, ringLen));ans addVectors(ans, lineToLine(n, x, y, leftLineLen, rightLineLen));// 乘以2因为是有序对 (i,j) 和 (j,i) 都算for (int i 0; i n; i) {ans[i] * 2;}return ans;}/*** 两个房屋都在环内的贡献* 环内距离为 min(|i-j|, ringLen - |i-j|)*/private long[] bothInRing(int n, int ringLen) {long[] res new long[n];// 对于距离 k (1 k (ringLen-1)/2)每对距离为k的有 ringLen 对for (int k 1; k (ringLen - 1) / 2; k) {res[k - 1] ringLen;}// 如果环长为偶数中间对称点只有 ringLen/2 对if (ringLen % 2 0) {res[ringLen / 2 - 1] ringLen / 2;}return res;}/*** 两个房屋在同一条链上的贡献左链或右链* 链上距离就是 |i-j|*/private long[] bothInTheSameLine(int n, int lineLen) {long[] res new long[n];// 距离为k的无序对有 lineLen - k 个for (int k 1; k lineLen; k) {res[k - 1] lineLen - k;}return res;}/*** 一个房屋在链上另一个在环内的贡献*/private long[] lineToRing(int n, int lineLen, int ringLen) {long[] res new long[n];// 最大可能距离for (int k 1; k lineLen ringLen; k) {// 在环内走的距离最多为 k-1留1给链且不超过 ringLen/2final int maxInRingLen Math.min(k - 1, ringLen / 2);// 在环内走的距离至少为0且至少为 k - lineLenfinal int minInRingLen Math.max(0, k - lineLen);if (minInRingLen maxInRingLen) {// 每个环内距离贡献2走环的上半部分或下半部分res[k - 1] (maxInRingLen - minInRingLen 1) * 2;// 如果 minInRingLen 0说明直接从链到x/y没有分叉减1if (minInRingLen 0) {res[k - 1] - 1;}// 如果 maxInRingLen * 2 ringLen中间对称点只算1次减1if (maxInRingLen * 2 ringLen) {res[k - 1] - 1;}}}return res;}/*** 一个房屋在左链另一个在右链的贡献*/private long[] lineToLine(int n, int x, int y, int leftLineLen, int rightLineLen) {long[] res new long[n];// 最大可能距离for (int k 1; k leftLineLen rightLineLen 2; k) {// 在左链走的距离最多为 leftLineLen且要给右链和环至少留空间final int maxInLeft Math.min(leftLineLen, k - 1 - (x y ? 1 : 0));// 在左链走的距离至少为1且至少为 k - rightLineLen - (xy?1:0)final int minInLeft Math.max(1, k - rightLineLen - (x y ? 1 : 0));if (minInLeft maxInLeft) {res[k - 1] maxInLeft - minInLeft 1;}}return res;}private long[] addVectors(long[] a, long[] b) {for (int i 0; i a.length; i) {a[i] b[i];}return a;}}---复杂度分析- 时间复杂度 O(n) — 每个循环最多遍历 O(n) 次- 空间复杂度 O(n) — 结果数组---参考来源- Doocs LeetCode 题解- walkccc 题解含 Java/C/Python 实现