C/C++算法-----------------------双指针详解技巧及例题

基本介绍

双指针（two poinnters）实际上是一种算法编程里的一种思想，它更像是一种编程思想，提供看非常高的算法效率，一般来说双指针指的是在遍历对象时使用两个或多个指针遍历进行操作，经常可以用来降低时间复杂度，那么双指针主要分为以下三种：

普通的指针：两个指针往一个方向移动
对撞指针：一般是在有序的情况下两个指针进行面对面的移动，适合解决约束条件的一组元素问题以及字符串反转问题
快慢指针：定义两个指针，一个快指针一个慢指针，用于判断是否为环或者长度的问题很方便

降低时间复杂度

假设我们有一个二维数组arr，大小为n x m，我们要对其进行双层循环遍历，原代码如下：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        // 执行操作
    }
}

1
2
3
4
5
6

我们使用双指针优化这个循环。首先，我们定义两个指针p1和p2，初始时分别指向数组的第一个元素。然后，我们使用一个循环来遍历数组，每次迭代更新指针的位置，并执行操作

int p1 = 0; // 第一个指针初始位置
int p2 = 0; // 第二个指针初始位置

while (p1 < n && p2 < m) {
    // 执行操作

    // 更新指针的位置
    p2++;
    if (p2 == m) {
        p2 = 0;
        p1++;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

这个例子将时间复杂度从O(n^2)降低到了O(n),需要注意的是，双指针优化适用于一些特定情况，例如对称矩阵、上三角矩阵或者二维数组中的某种特定模式，在其他情况下，双指针可能并不适用或者无法有效地优化时间复杂度，因此，在具体问题中，需要根据实际情况判断是否可以使用双指针优化，接下来看一个降低时间复杂度的例题：

降低时间复杂度例题

给定一个有序的递增数组，数组arr={1，3，4，9，11，12，14}，找到两个数之和为12，找到一组即可停止
思路：这题最容易想到的就是暴力算法，即直接两层循环嵌套逐个查找，但时间复杂度为：O(n^2)
暴力算法：

for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
	if(arr[i]+arr[j]==k)
	cout<<arr[i]<<arr[j]>>endl;
	}
}
1
2
3
4
5
6

双指针：这题使用双指针大大降低了时间复杂度

	int i = 0; // 从头开始的索引
	int j = arr.size() - 1; // 从尾开始的索引
	
while (i < j)
{
    if (arr[i] + arr[j] < k)
    {
        i++; // 如果arr[i]和arr[j]的和小于k，则增加i的值
    }
    else if (arr[i] + arr[j] > k)
    {
        j--; // 如果arr[i]和arr[j]的和大于k，则减小j的值
    }
    else
    {
        cout << arr[i] << arr[j] << endl; // 如果arr[i]和arr[j]的和等于k，则输出这两个数并结束循环
        break;
    }
}

return 0;


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

验证回文串

回文串：是指正向读和反向读都相同的字符串
很经典的题目，用双指针更能事半功倍，这里使用了对撞指针，即两个指针不断往中间靠拢，并对比是否相等，如果相等并且比较完了则代表是回文串

bool isPalindrome(string s) {
    // 定义左右指针
    int left = 0;
    int right = s.length() - 1;
    // 循环进行比较，直到两个指针相遇
    while (left < right) {
        // 跳过非字母和数字字符，只比较字母和数字字符
        if (!isalnum(s[left])) {
            left++;
            continue;
        }
        if (!isalnum(s[right])) {
            right--;
            continue;
        }
        // 将字符转换为小写比较
        if (tolower(s[left]) != tolower(s[right])) {
            return false; // 不是回文串，直接返回false
        }
        // 移动指针继续比较下一对字符
        left++;
        right--;
    }
    return true; // 是回文串，返回true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

判断是否为环

力扣第LeetCode第141.环形链表：https://leetcode.cn/problems/linked-list-cycle/description/
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false
示例 1：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 检查链表是否为空，如果为空则返回 false
        if (head == NULL)
            return false;
        // 初始化慢指针和快指针，开始位置都是头节点的位置
        ListNode* solt = head;
        ListNode* fast = head->next;
        // 循环遍历链表，直到慢指针和快指针相遇或者快指针到达链表末尾
        while (solt != fast) {
            // 如果快指针到达链表末尾或者倒数第二个节点，则表示链表没有环，返回 false
            if (fast == NULL || fast->next == NULL)
                return false; 
            // 更新慢指针和快指针的位置
            solt = solt->next;
            fast = fast->next->next;
        }
        // 如果循环结束后慢指针和快指针相遇，则表示链表有环，返回 true
        return true;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

对于上诉的问题我们可以使用双指针中的快慢指针来判断是否为环，定义一个一次走一步的指针solt和一次走两步的指针fast，从起点开始如果存在为环的话fast指针一定能追上solt即再次相遇，若相遇了则代表为环，快慢指针对于判断是否为环的情况下效率很高

反转链表

力扣LCR. 024.反转链表：https://leetcode.cn/problems/UHnkqh/description/
给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 如果链表为空或者只有一个节点，直接返回head（因为不需要反转）
        if (!head || !head->next) {
            return head;
        }

        ListNode* prev = nullptr;  // 用于存储当前节点的前一个节点
        ListNode* curr = head;      // 当前节点
        while (curr) {
            ListNode* nextNode = curr->next;  // 临时保存下一个节点的指针
            curr->next = prev;                // 反转指针，将当前节点指向前一个节点
            prev = curr;                      // 更新prev指针为当前节点
            curr = nextNode;                  // 更新curr指针为下一个节点
        }

        return prev;  // 返回反转后的头节点
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这道题使用了双指针：
prev指针用于存储当前节点的前一个节点，在代码中初始化为nullptr，表示当前节点没有前一个节点。
1.curr指针用于遍历链表，初始时指向头节点。
2.在循环中，首先将curr的下一个节点保存到临时变量nextNode中，以便后续使用。
3.接着将curr的next指针指向prev，实现了指针的反转。
4.然后更新prev为curr，将curr指针移动到下一个节点nextNode。
重复上述步骤直至遍历完整个链表。

总结

以上就是关于双指针的案例及分析，双指针并不是一种数据结构而是一种很经典的算法思想，可以通过它解决很多问题，其核心思想是设计一个不同速度、不同间距、及不同方向的两个指针来解决问题，在具体问题中，需要根据实际情况判断是否可以使用双指针，最重要的还是多刷题