双指针算法概念

2023-12-15 20:59 由小姜吃小僵发表于 #后端开发

"双指针"是一种在数组或链表中使用两个指针来进行操作的技术。这两个指针通常被称为“快”指针和“慢”指针，或者“左”指针和“右”指针，根据其在数据结构中的移动速度或位置来命名。
双指针算法在处理数组或链表的问题中非常有效，可以帮助我们以更优的时间复杂度解决问题。常见的应用包括两数之和、判断链表是否存在环、找到链表的中间节点等。
双指针可以分为以下几种类型：

同向双指针：两个指针都从同一侧开始移动，直到其中一个或两个达到终点。这种策略可以用来解决例如“移除元素”、“最大连续子序列和”等问题。
相向双指针：两个指针分别从两侧开始，向中间靠拢，直到两个指针相遇。这种策略可以用来解决例如“两数之和”、“回文字符串判断”等问题。
快慢双指针：两个指针以不同速度移动，快指针移动的速度是慢指针的两倍。这种策略常用来解决例如“是否存在环”、“找到中间节点”等问题。

无论使用哪种类型的双指针，关键都在于设定好指针移动的规则，从而减少不必要的计算和遍历，提升算法效率。

双指针算法在 C++ 中是一种常见的算法优化策略。如其名，这意味着在算法中，我们使用两个同类型的指针，通常是在一个数组或链表中。

这种方法主要用于序列或链表的遍历，可以减少时间复杂度，降低问题的复杂性。常见的使用情况有逆序数组，找到数组中的两数之和等问题。

下面我将展示一个代码示例，题目是在排序数组中找出两个数，使它们的和等于目标数。这是一个典型的双指针算法的使用场景。

#include<bits/stdc++.h>
using namespace std;

vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    while (left < right) {
        if (numbers[left] + numbers[right] == target) {
            return {left + 1, right + 1};
        } else if (numbers[left] + numbers[right] < target) {
            ++left;
        } else {
            --right;
        }
    }
    return {-1, -1};
}

int main() {
    vector<int> numbers = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSum(numbers, target);
    cout << "Index1: " << result[0] << ", Index2: " << result[1] << endl;
    return 0;
}

在上述代码中，我们使用双指针技术，左指针从数组起始位置开始，右指针从数组最后位置开始，因为给出的数组是排序好的，所以如果两个指针指向的两数之和小于目标数，那么左指针右移；如果两数之和大于目标数，那么右指针左移，如此循环直到找到符合条件的两数。