根据搜索结果我为你整理了 LeetCode 3017 的 C 语言实现。这道题的核心思路是将图结构分解为环和两条链然后分类讨论 6 种房屋对位置关系。---LeetCode 3017. 按距离统计房屋对数目 II题目描述给定 n 个房屋编号 1n房屋 i 与 i1 之间有街道相连额外有一条街道连接房屋 x 和 y。对于每个 k1 k n返回距离恰好为 k 的有序房屋对数量。约束 2 n 10^51 x, y n---C 语言实现c#include stdlib.h/*** 辅助函数将数组 b 加到数组 a 上*/static void addVectors(long long* a, const long long* b, int n) {for (int i 0; i n; i) {a[i] b[i];}}/*** 两个房屋都在环内的贡献* 环内距离为 min(|i-j|, ringLen - |i-j|)*/static long long* bothInRing(int n, int ringLen) {long long* res (long long*)calloc(n, sizeof(long long));// 对于距离 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|*/static long long* bothInTheSameLine(int n, int lineLen) {long long* res (long long*)calloc(n, sizeof(long long));// 距离为k的无序对有 lineLen - k 个for (int k 1; k lineLen; k) {res[k - 1] lineLen - k;}return res;}/*** 一个房屋在链上另一个在环内的贡献*/static long long* lineToRing(int n, int lineLen, int ringLen) {long long* res (long long*)calloc(n, sizeof(long long));// 最大可能距离for (int k 1; k lineLen ringLen; k) {// 在环内走的距离最多为 k-1留1给链且不超过 ringLen/2int maxInRingLen (k - 1 ringLen / 2) ? (k - 1) : (ringLen / 2);// 在环内走的距离至少为0且至少为 k - lineLenint minInRingLen (0 k - lineLen) ? 0 : (k - lineLen);if (minInRingLen maxInRingLen) {// 每个环内距离贡献2走环的上半部分或下半部分res[k - 1] (long long)(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;}/*** 一个房屋在左链另一个在右链的贡献*/static long long* lineToLine(int n, int x, int y, int leftLineLen, int rightLineLen) {long long* res (long long*)calloc(n, sizeof(long long));int xyGap (x y) ? 1 : 0;// 最大可能距离for (int k 1; k leftLineLen rightLineLen 2; k) {// 在左链走的距离最多为 leftLineLen且要给右链和环至少留空间int maxInLeft (leftLineLen k - 1 - xyGap) ? leftLineLen : (k - 1 - xyGap);// 在左链走的距离至少为1且至少为 k - rightLineLen - xyGapint minInLeft (1 k - rightLineLen - xyGap) ? 1 : (k - rightLineLen - xyGap);if (minInLeft maxInLeft) {res[k - 1] maxInLeft - minInLeft 1;}}return res;}/*** Note: The returned array must be malloced, assume caller calls free().*/long long* countOfPairs(int n, int x, int y, int* returnSize) {// 确保 x yif (x y) {int temp x;x y;y temp;}const int ringLen y - x 1; // 环的长度const int leftLineLen x - 1; // 左链长度const int rightLineLen n - y; // 右链长度long long* ans (long long*)calloc(n, sizeof(long long));// 分别计算6种情况的贡献long long* temp;temp bothInRing(n, ringLen);addVectors(ans, temp, n);free(temp);temp bothInTheSameLine(n, leftLineLen);addVectors(ans, temp, n);free(temp);temp bothInTheSameLine(n, rightLineLen);addVectors(ans, temp, n);free(temp);temp lineToRing(n, leftLineLen, ringLen);addVectors(ans, temp, n);free(temp);temp lineToRing(n, rightLineLen, ringLen);addVectors(ans, temp, n);free(temp);temp lineToLine(n, x, y, leftLineLen, rightLineLen);addVectors(ans, temp, n);free(temp);// 乘以2因为是有序对 (i,j) 和 (j,i) 都算for (int i 0; i n; i) {ans[i] * 2;}*returnSize n;return ans;}---思路说明图的结构可以分解为部分 范围 长度左链 [1, x) leftLineLen x - 1环 [x, y] ringLen y - x 1右链 (y, n] rightLineLen n - y需要分类讨论以下 6 种房屋对位置关系 1. bothInRing两个房屋都在环内2. bothInTheSameLine两个房屋都在左链或都在右链3. lineToRing一个房屋在左链/右链另一个在环内两种情况4. lineToLine一个房屋在左链另一个在右链最后将各情况结果相加并乘以 2因为是有序对。---复杂度分析- 时间复杂度 O(n) — 每个循环最多遍历 O(n) 次- 空间复杂度 O(n) — 结果数组及中间临时数组---参考来源- walkccc 题解含 C/Java/Python 实现- LeetCode 官方题解含 C 实现