在C++編程中，雙指針?biāo)惴ㄊ且环N高效的解題思路，其核心是通過(guò)設(shè)置兩個(gè)指針（或索引）遍歷數(shù)據(jù)結(jié)構(gòu)（如數(shù)組、鏈表、字符串等），利用指針的移動(dòng)規(guī)則減少無(wú)效操作，從而將時(shí)間復(fù)雜度從暴力解法的O(n²)優(yōu)化至O(n)或O(n log n)。這種算法廣泛應(yīng)用于鏈表操作、數(shù)組處理、字符串匹配等場(chǎng)景。

一、雙指針?biāo)惴ǖ暮诵乃枷?/h2>

雙指針?biāo)惴ǖ谋举|(zhì)是通過(guò)兩個(gè)指針的協(xié)同移動(dòng)，縮小問(wèn)題的處理范圍。與暴力解法中嵌套循環(huán)的“盲目遍歷”不同，雙指針的移動(dòng)具有明確的邏輯（如基于數(shù)據(jù)的有序性、結(jié)構(gòu)特性等），從而避免冗余計(jì)算。

其核心優(yōu)勢(shì)體現(xiàn)在：

• 時(shí)間優(yōu)化：將多層循環(huán)轉(zhuǎn)化為單層遍歷，降低時(shí)間復(fù)雜度；
• 空間優(yōu)化：多數(shù)情況下無(wú)需額外空間（原地操作），空間復(fù)雜度可保持O(1)；
• 邏輯清晰：通過(guò)指針的移動(dòng)規(guī)則直觀反映問(wèn)題的解決思路。

二、雙指針的常見(jiàn)類(lèi)型及應(yīng)用場(chǎng)景

根據(jù)指針的移動(dòng)方向和作用，雙指針可分為三大類(lèi)：快慢指針、左右指針、同向指針。以下結(jié)合具體場(chǎng)景詳細(xì)講解。

（一）快慢指針（Floyd’s Tortoise and Hare）

快慢指針指兩個(gè)指針以不同速度遍歷數(shù)據(jù)結(jié)構(gòu)（如鏈表中，快指針每次走2步，慢指針每次走1步）。其核心應(yīng)用是處理鏈表中的環(huán)問(wèn)題和查找特定位置（如中間節(jié)點(diǎn)）。

1. 鏈表環(huán)檢測(cè)（LeetCode 141）

問(wèn)題：判斷一個(gè)單鏈表是否存在環(huán)。
暴力解法：用哈希表記錄訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)，若重復(fù)訪(fǎng)問(wèn)則有環(huán)，時(shí)間O(n)但空間O(n)。
雙指針解法：

• 設(shè)快指針fast和慢指針slow，初始均指向頭節(jié)點(diǎn)；
• fast每次移動(dòng)2步，slow每次移動(dòng)1步；
• 若鏈表有環(huán)，fast會(huì)先進(jìn)入環(huán)并繞環(huán)移動(dòng)，最終與slow在環(huán)內(nèi)相遇；
• 若fast到達(dá)nullptr，則無(wú)環(huán)。

代碼實(shí)現(xiàn)：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

bool hasCycle(ListNode *head) {
    if (head == nullptr || head->next == nullptr) return false;
    ListNode *slow = head;
    ListNode *fast = head->next; // 初始錯(cuò)開(kāi)，避免直接相遇
    while (slow != fast) {
        if (fast == nullptr || fast->next == nullptr) return false;
        slow = slow->next;       // 慢指針走1步
        fast = fast->next->next; // 快指針走2步
    }
    return true;
}

時(shí)間復(fù)雜度：O(n)（無(wú)環(huán)時(shí)fast走n/2步；有環(huán)時(shí)相遇前slow最多走n步）。
空間復(fù)雜度：O(1)（僅用兩個(gè)指針）。

2. 尋找環(huán)的入口（LeetCode 142）

問(wèn)題：若鏈表有環(huán)，找到環(huán)的入口節(jié)點(diǎn)。
算法思路：

1. 先用快慢指針判斷有環(huán)，記錄相遇點(diǎn)meet；
2. 讓slow從頭節(jié)點(diǎn)出發(fā)，fast從meet出發(fā)，兩者均每次走1步；
3. 兩指針再次相遇的節(jié)點(diǎn)即為環(huán)的入口。

原理：設(shè)頭節(jié)點(diǎn)到入口距離為a，入口到相遇點(diǎn)距離為b，環(huán)長(zhǎng)為c。則相遇時(shí)：

• slow走了a + b；
• fast走了a + b + k*c（繞環(huán)k圈）；
• 因fast速度是slow的2倍，故2*(a + b) = a + b + k*c → a = k*c - b b=k*c-a。
• 因此，slow從頭部走a步，與fast從meet走k*c - b步（等價(jià)于繞環(huán)k圈后回到入口）相遇。

重置slow = 0,fast仍在meet處（等價(jià)于初始走了a+b），當(dāng)slow=a(slow走了a步)，fast=a+b+kc-b=a+kc，所以a,b在環(huán)的入口相遇

代碼實(shí)現(xiàn)：

ListNode *detectCycle(ListNode *head) {
    if (head == nullptr) return nullptr;
    ListNode *slow = head, *fast = head;
    // 第一步：找到相遇點(diǎn)
    do {
        if (fast->next == nullptr || fast->next->next == nullptr) return nullptr;
        slow = slow->next;
        fast = fast->next->next;
    } while (slow != fast);
    // 第二步：尋找入口
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return fast;
}

3. 尋找鏈表的中間節(jié)點(diǎn)（LeetCode 876）

問(wèn)題：返回單鏈表的中間節(jié)點(diǎn)（若長(zhǎng)度為偶數(shù)，返回第二個(gè)中間節(jié)點(diǎn)）。
算法思路：

• 快指針每次走2步，慢指針每次走1步；
• 當(dāng)fast到達(dá)尾節(jié)點(diǎn)時(shí)，slow恰好指向中間節(jié)點(diǎn)。

代碼實(shí)現(xiàn)：

ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

（二）左右指針（相向指針）

左右指針指兩個(gè)指針?lè)謩e從數(shù)據(jù)結(jié)構(gòu)的兩端出發(fā)，相向而行（左指針從左向右，右指針從右向左），多用于有序數(shù)組/字符串的處理。其核心是利用數(shù)據(jù)的有序性，通過(guò)指針移動(dòng)排除無(wú)效解。

1. 兩數(shù)之和（有序數(shù)組版，LeetCode 167）

問(wèn)題：給定有序數(shù)組nums和目標(biāo)值target，找到兩個(gè)數(shù)使得和為target，返回索引（下標(biāo)從1開(kāi)始）。
暴力解法：嵌套循環(huán)遍歷所有組合，時(shí)間O(n²)。
雙指針解法：

• 左指針left初始指向0，右指針right指向n-1；
• 計(jì)算當(dāng)前和sum = nums[left] + nums[right]：
  • 若sum == target，返回[left+1, right+1]；
  • 若sum > target，說(shuō)明右指針太大，right--；
  • 若sum < target，說(shuō)明左指針太小，left++。

原理：數(shù)組有序保證了指針移動(dòng)的有效性——當(dāng)sum > target時(shí)，減小右指針可降低總和；當(dāng)sum < target時(shí)，增大左指針可提高總和，無(wú)需檢查其他組合。

代碼實(shí)現(xiàn)：

vector<int> twoSum(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            return {left + 1, right + 1};
        } else if (sum > target) {
            right--;
        } else {
            left++;
        }
    }
    return {-1, -1}; // 題目保證有解，此行為冗余
}

時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度O(1)。

2. 反轉(zhuǎn)字符串（LeetCode 344）

問(wèn)題：原地反轉(zhuǎn)字符串（如["h","e","l","l","o"]→["o","l","l","e","h"]）。
算法思路：

• 左指針left指向0，右指針right指向n-1；
• 交換nums[left]與nums[right]，然后left++、right--，直到left >= right。

代碼實(shí)現(xiàn)：

void reverseString(vector<char>& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        swap(s[left], s[right]);
        left++;
        right--;
    }
}

3. 二分查找（本質(zhì)是左右指針的變體）

二分查找中，left和right指針?lè)謩e指向搜索范圍的兩端，通過(guò)比較中間值與目標(biāo)值，不斷縮小范圍，本質(zhì)是左右指針的“跳躍式移動(dòng)”。

代碼實(shí)現(xiàn)：

int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // 避免溢出
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

（三）同向指針（一前一后指針）

同向指針指兩個(gè)指針從同一端出發(fā)，沿相同方向移動(dòng)（通常一個(gè)在前“探索”，一個(gè)在后“記錄”），多用于數(shù)組去重、子數(shù)組/子串問(wèn)題。

1. 刪除有序數(shù)組中的重復(fù)項(xiàng)（LeetCode 26）

問(wèn)題：原地刪除有序數(shù)組中的重復(fù)元素，返回新長(zhǎng)度（如[1,1,2]→長(zhǎng)度2，數(shù)組變?yōu)?code>[1,2]）。
算法思路：

• 慢指針slow記錄有效元素的尾位置（初始0）；
• 快指針fast遍歷數(shù)組（初始1）；
• 若nums[fast] != nums[slow]，說(shuō)明找到新元素，slow++并將nums[fast]復(fù)制到nums[slow]；
• 最終slow + 1為新長(zhǎng)度。

代碼實(shí)現(xiàn)：

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int slow = 0;
    for (int fast = 1; fast < nums.size(); fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

2. 移動(dòng)零（LeetCode 283）

問(wèn)題：將數(shù)組中的0移到末尾，保持非零元素的相對(duì)順序（如[0,1,0,3,12]→[1,3,12,0,0]）。
算法思路：

• 慢指針slow記錄非零元素的尾位置（初始0）；
• 快指針fast遍歷數(shù)組，若nums[fast] != 0，則交換nums[slow]與nums[fast]，slow++；
• 遍歷結(jié)束后，slow及之后的位置全部賦0。

代碼實(shí)現(xiàn)：

void moveZeroes(vector<int>& nums) {
    int slow = 0;
    for (int fast = 0; fast < nums.size(); fast++) {
        if (nums[fast] != 0) {
            swap(nums[slow], nums[fast]);
            slow++;
        }
    }
    // 剩余位置補(bǔ)0（可選，因原數(shù)組0已被交換到后面）
    for (int i = slow; i < nums.size(); i++) {
        nums[i] = 0;
    }
}

3. 滑動(dòng)窗口（同向指針的高級(jí)應(yīng)用）

滑動(dòng)窗口是同向指針的典型場(chǎng)景，用于解決子數(shù)組/子串的最值問(wèn)題（如最長(zhǎng)、最短、包含特定元素等）。其核心是用left和right指針維護(hù)一個(gè)“窗口”，通過(guò)移動(dòng)right擴(kuò)張窗口，移動(dòng)left收縮窗口，在O(n)時(shí)間內(nèi)找到最優(yōu)解。

示例：長(zhǎng)度最小的子數(shù)組（LeetCode 209）
問(wèn)題：給定數(shù)組nums和目標(biāo)值s，找到和≥s的最短子數(shù)組長(zhǎng)度（若無(wú)則返回0）。

算法思路：

• left和right初始均為0，sum記錄窗口內(nèi)元素和；
• 移動(dòng)right，將nums[right]加入sum；
• 當(dāng)sum ≥ s時(shí)，嘗試移動(dòng)left縮小窗口，更新最小長(zhǎng)度；
• 重復(fù)直至right遍歷結(jié)束。

代碼實(shí)現(xiàn)：

int minSubArrayLen(int s, vector<int>& nums) {
    int n = nums.size();
    int min_len = INT_MAX;
    int left = 0, sum = 0;
    for (int right = 0; right < n; right++) {
        sum += nums[right];
        // 收縮窗口
        while (sum >= s) {
            min_len = min(min_len, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return min_len == INT_MAX ? 0 : min_len;
}

時(shí)間復(fù)雜度：O(n)（每個(gè)元素被right和left各訪(fǎng)問(wèn)一次）。

三、雙指針?biāo)惴ǖ倪M(jìn)階技巧

1. 指針初始化的靈活性：
   快慢指針初始可不同步（如環(huán)檢測(cè)中fast比slow超前一步）；左右指針可從非端點(diǎn)出發(fā)（如處理子數(shù)組時(shí)限制窗口范圍）。

2. 結(jié)合數(shù)據(jù)結(jié)構(gòu)特性：
   有序數(shù)組優(yōu)先考慮左右指針；鏈表問(wèn)題優(yōu)先考慮快慢指針；子串問(wèn)題優(yōu)先考慮滑動(dòng)窗口（同向指針）。

3. 多指針擴(kuò)展：
   某些場(chǎng)景需3個(gè)指針（如荷蘭國(guó)旗問(wèn)題：用left、mid、right劃分0、1、2），核心思想與雙指針一致。

4. 邊界條件處理：
   需注意指針越界（如鏈表fast->next是否為nullptr）、空數(shù)據(jù)結(jié)構(gòu)（如數(shù)組長(zhǎng)度為0）等特殊情況。

雙指針?biāo)惴ㄊ荂++編程中優(yōu)化效率的核心思想之一，其核心在于通過(guò)指針的協(xié)同移動(dòng)減少無(wú)效遍歷。根據(jù)應(yīng)用場(chǎng)景可分為快慢指針（鏈表環(huán)、中間節(jié)點(diǎn)）、左右指針（有序數(shù)組、反轉(zhuǎn)）、同向指針（去重、滑動(dòng)窗口）三大類(lèi)，每種類(lèi)型均通過(guò)明確的移動(dòng)規(guī)則將時(shí)間復(fù)雜度從O(n²)降至O(n)。

到此這篇關(guān)于C++雙指針的實(shí)踐的文章就介紹到這了,更多相關(guān)C++雙指針內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論