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

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

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

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

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

二、雙指針的常見類型及應(yīng)用場景

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

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

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

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

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

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

代碼實現(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; // 初始錯開，避免直接相遇
    while (slow != fast) {
        if (fast == nullptr || fast->next == nullptr) return false;
        slow = slow->next;       // 慢指針走1步
        fast = fast->next->next; // 快指針走2步
    }
    return true;
}

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

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

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

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

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

• 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步（等價于繞環(huán)k圈后回到入口）相遇。

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

代碼實現(xiàn)：

ListNode *detectCycle(ListNode *head) {
    if (head == nullptr) return nullptr;
    ListNode *slow = head, *fast = head;
    // 第一步：找到相遇點
    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é)點（LeetCode 876）

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

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

代碼實現(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;
}

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

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

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

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

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

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

代碼實現(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}; // 題目保證有解，此行為冗余
}

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

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

問題：原地反轉(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。

代碼實現(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指針分別指向搜索范圍的兩端，通過比較中間值與目標(biāo)值，不斷縮小范圍，本質(zhì)是左右指針的“跳躍式移動”。

代碼實現(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;
}

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

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

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

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

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

代碼實現(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. 移動零（LeetCode 283）

問題：將數(shù)組中的0移到末尾，保持非零元素的相對順序（如[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。

代碼實現(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. 滑動窗口（同向指針的高級應(yīng)用）

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

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

算法思路：

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

代碼實現(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;
}

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

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

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

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

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

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

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

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

最新評論