跳转至

双指针算法及其应用

双指针是一种重要的算法技巧，它通过使用两个指针在数据结构中移动来解决问题，通常能将时间复杂度从\(O(n^2)\)优化到\(O(n)\)。

基本概念

双指针主要有3种类型：

  1. 同向双指针：两个指针从同一侧出发，通常是从开头，按照一定条件向同一方向移动。
  2. 对向双指针：两个指针从数组的两端向中间移动。
  3. 背向双指针：两个指针从相同或者相邻的位置出发，背向移动直到其中一根指针到达边界为止。

常见应用场景

1. 快慢指针

快慢指针主要用于解决链表中的问题：

  • 检测链表中的环：快指针每次移动两步，慢指针每次移动一步，如果存在环，两指针最终会相遇
bool hasCycle(ListNode *head) {
    if (!head || !head->next) return false;
    ListNode *slow = head, *fast = head->next;
    while (slow != fast) {
        if (!fast || !fast->next) return false;
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}
  • 寻找链表的中间节点：快指针每次移动两步，慢指针每次移动一步，当快指针到达尾部时，慢指针正好在中间
ListNode* middleNode(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

2. 滑动窗口

滑动窗口是同向双指针的一种特殊形式。

3. 对向双指针

  • 两数之和：在有序数组中找到和为目标值的两个数
vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) return {left + 1, right + 1};
        else if (sum < target) left++;
        else right--;
    }
    return {};
}
  • 三数之和：找到和为0的三个数
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;
}

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int maxArea = 0;
    while (left < right) {
        maxArea = max(maxArea, min(height[left], height[right]) * (right - left));
        if (height[left] < height[right]) left++;
        else right--;
    }
    return maxArea;
}

4. 同向双指针

  • 移除数组中的元素：移除指定值并返回新长度
int removeElement(vector<int>& nums, int val) {
    int i = 0;
    for (int j = 0; j < nums.size(); j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
}

[!NOTE] 可以看看Rust中Vector::retain函数，使用了类似的算法。

  • 颜色分类：将红白蓝三种颜色排序（荷兰国旗问题）
void sortColors(vector<int>& nums) {
    int p0 = 0, curr = 0, p2 = nums.size() - 1;
    while (curr <= p2) {
        if (nums[curr] == 0) {
            swap(nums[p0++], nums[curr++]);
        } else if (nums[curr] == 2) {
            swap(nums[curr], nums[p2--]);
        } else {
            curr++;
        }
    }
}

技巧总结

  1. 识别机会：当问题涉及数组/字符串的线性遍历或查找，考虑是否能用双指针
  2. 指针移动条件：明确定义何时移动左指针和右指针的条件
  3. 边界处理：注意数组边界和特殊情况
  4. 去重技巧：在需要避免重复结果的场景中，移动指针时跳过重复元素

双指针技巧是解决数组、字符串和链表问题的有力工具，掌握它能显著提高解题效率。