指標之間題解

簡潔題意

實作 int count_between(int *a, int *b);。兩個指標指向同一個陣列中的元素，請回傳兩個位置中間夾了幾個元素，不含兩個端點。指標的先後順序不保證。

這一題完全不用碰值

交換指標指向的整數練的是用 *a 改到位置上的值。這一題相反：值長什麼樣子完全不重要，要算的是兩個位置離多遠。

11.2 教過，同一個陣列裡的兩個指標可以相減，而且相減的單位是元素個數，不是位元組：

int a[10];
int *p = &a[2];
int *q = &a[7];
cout << q - p << '\n';   // 5

q - p 是 \(5\)，意思是「從 p 走到 q 要跨 \(5\) 步」。

從距離到答案

拿範例 1 的第一筆來看：兩個指標指向第 \(2\) 格與第 \(5\) 格，距離是 \(3\)，中間夾的是第 \(3\)、第 \(4\) 格共 \(2\) 個。

距離 \(3\)、答案 \(2\)——跨過去的每一步都會踩過一個新格子，但最後那一步踩到的是端點本身，不能算。所以答案是距離減 \(1\)。

兩個特殊情況順著這個想法就通了：

相鄰兩格：距離 \(1\)，減 \(1\) 得 \(0\)，中間確實沒東西（範例 1 第二筆）。
同一格：距離 \(0\)，這時候不能再減 \(1\)，答案直接是 \(0\)（範例 1 第三筆）。

最後一件事：題目沒保證 a 在 b 左邊。a - b 可能是負的，先把它變成非負再往下算。

每次呼叫只做固定次數的運算，時間複雜度 \(O(1)\)。

參考程式碼

int count_between(int *a, int *b) {
    int distance = a - b;      // 兩個位置之間差幾格
    if (distance < 0) {
        distance = -distance;  // 不管誰在左邊，距離都當成正的
    }
    if (distance == 0) {
        return 0;              // 指向同一格，中間夾 0 個
    }
    return distance - 1;       // 扣掉「跨過去那一步」
}

常犯錯誤

回傳距離本身，忘了減 \(1\)：範例 1 第一筆會印 3，正解是 2。
直接寫 b - a - 1：假設了 a 一定在左邊。範例 2 第一筆（第 \(9\) 格與第 \(2\) 格）印出 -8；而且兩個指標指同一格時會得到 -1，範例 1 第三筆就掛了。
拿 *a - *b 相減：那是兩個格子裡的數字相減。格子裡放的是什麼數字，跟它排在第幾格是兩回事，評分程式也不會讓它們剛好相等——範例 1 第一筆會印出 110。

接下來

到這裡，指標的兩個基本動作都用過了：*p 取值寫值、指標相減算距離。指標陣列加總會把「位置」本身當成資料存進陣列裡——那裡的每一格存的都是一個門牌號碼。

指標之間 題解