我来搜索 LeetCode 3017 这道题的详细信息和题解。

LeetCode 3017. 按距离统计房屋对数目 II

题目描述

给定 `n` 个房屋，编号从 `1` 到 `n`，排成一条直线。在房屋 `x` 和 `y` 之间有一条额外的街道连接。对于每个 `k`（`1 <= k <= n`），返回距离恰好为 `k` 的有序房屋对 `(house1, house2)` 的数量。

约束条件： `2 <= n <= 10^5`，`1 <= 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 实现

```java
class Solution {
    public long[] countOfPairs(int n, int x, int y) {
        // 确保 x <= y
        if (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/2
            final int maxInRingLen = Math.min(k - 1, ringLen / 2);
            // 在环内走的距离至少为0，且至少为 k - lineLen
            final int minInRingLen = Math.max(0, k - lineLen);
            
            if (minInRingLen <= maxInRingLen) {
                // 每个环内距离贡献2（走环的上半部分或下半部分）
                res[k - 1] += (maxInRingLen - minInRingLen + 1) * 2;
                // 如果 minInRingLen == 0，说明直接从链到x/y，没有分叉，减1
                if (minInRingLen == 0) {
                    res[k - 1] -= 1;
                }
                // 如果 maxInRingLen * 2 == ringLen，中间对称点只算1次，减1
                if (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 - (x<y?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 实现）