双指针法总结|dc的house

双指针法是算法中非常常用的一种技巧，尤其在数组、字符串和链表的操作中，双指针法能够显著提高算法的效率。本文将从数组、字符串、链表以及N数之和等多个方面，详细总结双指针法的应用场景和实现技巧，并结合代码示例帮助大家更好地理解和掌握这一重要的算法思想。

1. 数组篇：移除元素

在数组中，移除元素是一个常见的操作。由于数组的内存是连续的，不能直接删除元素，只能通过覆盖来实现。如果使用暴力方法，可能会导致时间复杂度较高。

1.1 暴力解法的问题

以下是一个暴力解法的伪代码：

for (int i = 0; i < array.size(); i++) {
    if (array[i] == target) {
        array.erase(i);
    }
}

这个代码的时间复杂度看似是O(n)，但实际上erase操作的时间复杂度是O(n)，因此整体时间复杂度为O(n^2)。

1.2 双指针法的优势

使用双指针法可以将时间复杂度降低到O(n)。具体思路是：

定义一个快指针fast和一个慢指针slow。
快指针用于遍历数组，慢指针用于记录新数组的下标。
当快指针指向的元素不等于目标值时，将其赋值给慢指针指向的位置。

以下是代码实现：

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

2. 字符串篇：反转与替换

双指针法在字符串操作中也有广泛的应用，例如反转字符串和替换空格。

2.1 反转字符串

反转字符串是一个经典的双指针问题。定义两个指针，一个指向字符串的开头，另一个指向字符串的末尾，然后交换两个指针指向的字符，直到两个指针相遇。

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

2.2 替换空格

替换空格的问题也可以通过双指针法高效解决。具体思路是：

统计字符串中的空格数量，扩充字符串的大小。
使用双指针从后向前替换空格。

string replaceSpaces(string s) {
    int count = 0;
    for (char c : s) {
        if (c == ' ') count++;
    }
    int oldSize = s.size();
    s.resize(s.size() + count * 2);
    int newSize = s.size();
    for (int i = oldSize - 1, j = newSize - 1; i >= 0; i--, j--) {
        if (s[i] != ' ') {
            s[j] = s[i];
        } else {
            s[j] = '0';
            s[j - 1] = '2';
            s[j - 2] = '%';
            j -= 2;
        }
    }
    return s;
}

3. 链表篇：翻转与环检测

双指针法在链表操作中也有重要的应用，例如翻转链表和检测链表中的环。

3.1 翻转链表

翻转链表是面试中的经典问题。使用双指针法可以高效地完成链表的翻转。

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

ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

3.2 检测链表中的环

检测链表中的环是双指针法的另一个经典应用。通过快慢指针可以判断链表中是否存在环，并找到环的入口。

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            ListNode* ptr = head;
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;
        }
    }
    return nullptr;
}

4. N数之和篇：双指针法的经典应用

双指针法在解决N数之和问题时非常高效，尤其是在三数之和和四数之和的问题中。

4.1 两数之和

两数之和问题可以通过哈希表解决，但双指针法也可以用于解决类似的问题。

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i];
        if (map.find(complement) != map.end()) {
            return {map[complement], i};
        }
        map[nums[i]] = i;
    }
    return {};
}

4.2 三数之和

三数之和问题可以通过双指针法将时间复杂度从O(n^3)降低到O(n^2)。

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum < 0) {
                left++;
            } else if (sum > 0) {
                right--;
            } else {
                result.push_back({nums[i], nums[left], nums[right]});
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            }
        }
    }
    return result;
}

4.3 四数之和

四数之和问题可以通过在三数之和的基础上再套一层循环来解决。

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j < nums.size(); j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            int left = j + 1, right = nums.size() - 1;
            while (left < right) {
                long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    result.push_back({nums[i], nums[j], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }
        }
    }
    return result;
}