算法-双指针专题

文章目录

概念
- 应用场景：
- 常见问题类型：
对向指针模型
同向指针模型
多序列模型

概念

双指针法是一种常用的算法思想，通常用于解决数组或链表相关的问题。该方法的核心思想是使用两个指针在数据结构中按照一定的规则移动，以解决问题或寻找特定的解。这两个指针可以按照不同的方式移动：一起移动、相向移动、同向移动等。下面我将详细介绍双指针思想的应用场景以及常见的问题类型。

应用场景：

数组或链表中的查找：双指针可以用来在有序或无序数组中查找满足某种条件的元素或子数组。例如，可以使用双指针找到数组中的两个数之和等于目标值的组合，或者找到链表中倒数第 k 个节点。
数组或链表中的倒序遍历：当需要在数组或链表中倒序遍历时，双指针可以是一个有效的选择。例如，需要将链表反转或者数组中的元素按某种条件倒序排列。
滑动窗口：在数组或字符串中，有一类问题需要找出满足一定条件的子串，而且这个子串是连续的。例如，在一个字符串中找到最短的包含目标字符的子串，或者找到子数组的最大和不超过某个值。这种问题通常可以通过双指针来解决，其中一个指针用于扩展窗口，另一个指针用于收缩窗口。
链表中的环检测与环的起点：使用快慢指针可以检测链表中是否存在环，并且可以找到环的起点。

常见问题类型：

在数组中找到两个数之和等于目标值。
反转链表。
将两个有序数组合并为一个有序数组。
在有序数组或链表中删除重复元素。
在数组中找到可以盛水最多的容器。
检测链表中是否存在环。
找到字符串中包含目标子串的最短窗口。
找到字符串中最长的无重复字符子串。

双指针法是解决数组、链表等数据结构中一类特定问题的常用技巧。它通常能够以较低的时间复杂度解决问题，并且易于实现。通过灵活地控制指针的移动，可以解决各种不同类型的问题，包括查找、遍历、合并、移除等操作。

下面我们总结几种常用模型，并配上例题来讲解。

对向指针模型

两个指针，初始一个在左、一个在右，左指针向右移动，右指针向左移动，直到相撞停止。

适用场景：二分查找、反转数组、回文判定。

在这里插入图片描述

对于这个问题，我们进行遍历的时候就可以用两个指针，一个从前开始一个从后开始，那么很明显，我们指针移动有三种情况

找到了等于k等情况，此时low指针向后走，high指针向前
当前算的值比k大，那么让high向前走
当前算的值比k小，那么low指针应该向后走

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,k,a[N];

int main(){
	cin >> n >> k;
	for(int i = 0;i < n;i ++) cin >> a[i];
	int low = 0,high = n-1,sum = 0;
	while(low < high){
		if(a[low]+a[high] == k){
			sum++;
			high = high - 1;
			low = low + 1;
		}else if(a[low]+a[high] > k){
			high = high - 1;
		}else{
			low = low + 1;
		}
	}
	cout << sum;
	return 0;
}

同向指针模型

两个指针，初始在同一位置，然后向相同方向移动，一个移动速度快，一个移动速度慢。

适用场景：查找链表中间节点、链表是否包含环、原地修改数组。

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz

1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

那么对于我们这个问题，我们可以用两个指针去维护，一个慢指针，一个快指针，快慢指针始终保持n这个间距，那么快指针走到底的时候，慢指针指向的位置就是倒数第n个结点的位置

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
     ListNode* dummy = new ListNode(0, head);
    ListNode* slow = dummy;
    ListNode* fast = dummy;

    for (int i = 0; i < n + 1; i++) {
        fast = fast->next;
    }

    while (fast != nullptr) {
        slow = slow->next;
        fast = fast->next;
    }

    slow->next = slow->next->next;
    return dummy->next;
    }
};

多序列模型

我们上面介绍的都是仅限于单序列问题，下面我们介绍几种多个序列应用双指针的模型。

在这里插入图片描述
这种就是最基本的双序列合并问题，我们可以定义两个指针，分别指向序列1和序列2，然后开始遍历，如果序列1的data比序列2更小，那我们把序列1加入我们的新序列3中，然后让序列1的指针向前移动，如果我们遇到空的情况，那就直接让新序列接上另一段序列。

我这里用的是链表去实现，大家可以自己用数组去实现一下，数组会更好实现。

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

typedef struct node{
	int data;
	node *next;
}LNode,*LinkList;

int main(){
	int n,m,tmp;
	cin >> n >> m;
	LinkList l1 = (LinkList)malloc(sizeof(LNode));
	LinkList l2 = (LinkList)malloc(sizeof(LNode));
	LinkList l3 = (LinkList)malloc(sizeof(LNode));
	l1->next = NULL;
	l2->next = NULL;
	l3->next = NULL;
	LinkList r1 = l1,r2 = l2,r3 = l3;
	while(n--){
		cin >> tmp;
		LinkList tmpNode = (LinkList)malloc(sizeof(LNode));
		tmpNode->data = tmp;
		r1->next = tmpNode;
		r1 = r1->next;
	}
	r1->next = NULL;
	while(m--){
		cin >> tmp;
		LinkList tmpNode = (LinkList)malloc(sizeof(LNode));
		tmpNode->data = tmp;
		r2->next = tmpNode;
		r2 = r2->next;
	}
	r2->next = NULL;
	LinkList q = l1->next,p = l2->next;
	while(q&&p){
		if(p->data >= q->data){
			r3->next = q;
			q = q->next;
			r3 = r3->next;
		}else{
			r3->next = p;
			p = p->next;
			r3 = r3->next;
		}
	}
	r3->next = (p?p:q);
	LinkList s = l3->next;
	while(s){
		cout << s->data;
		s = s->next;
		if(s) cout << " ";
	}
}