双指针算法

本文主要是介绍双指针算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

理解

双指针基本只涉及到两种指针，一种是快慢指针，一种是对撞指针；
快慢指针主要解决有关链表一类的问题，如链表里是否有环，环状链表的长度等；而对撞指针一般解决二分等问题；
快慢指针一般是设计一个快指针和一个慢指针，一开始都指向链表的开头；而对撞指针一般是设计一头一尾两个速度相等的指针，最终会相遇。

快慢指针_应用场景_1

题意
判断一段链表是否存在环，并找出环入口结点
链接https://www.acwing.com/problem/content/description/86/
思路
一般多用于面试题；
单链表的特点是每个节点只知道下一个节点，所以一个指针的话无法判断链表中是否含有环的；
因此，设计一个每次前进两个节点的快指针和每次前进一个节点的慢指针，一开始都指向链表的开头；
如果链表中不包含环，那么这个指针最终会遇到空指针 null 表示链表到头了，可以判断该链表不含环。

如果有环，末尾的ne[4]就会指向一个节点，并且快慢指针最后一定会相遇。

代码模板

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if (!head || !head->next) return 0;
        ListNode *first = head, *second = head;

        while (first && second)
        {
            first = first->next;
            second = second->next;
            if (second) second = second->next;
            else return 0;

            if (first == second)
            {
                first = head;
                while (first != second)
                {
                    first = first->next;
                    second = second->next;
                }
                return first;
            }
        }

        return 0;
    }
};

快慢指针_应用场景_2

题意
题目链接：https://www.acwing.com/problem/content/801/
给定一个整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
思路
设置一对快慢指针，慢指针速度设计为0，快指针速度为每次前进一格，同时开一个数组记载数字的出现次数；
若出现重复的数字，记载该区间数字的长度，快指针进一格，慢指针到达重复数字的位置，并删去重复数字之前数字的个数；
从大佬那里拐来的图

代码模板

#include <iostream>
using namespace std;

const int N = 100010;
int a[N], count[N];
int n, ans;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) 
    {
        cin >> a[i];
    }
    for (int i = 0, j = 0; j < n; j++)
    {
        count[a[j]] ++;//记录出现次数
        //如果快指针所指向的数字出现了两次，则快指针停止前进，慢指针一路前进到快指针所指到的数字，并将沿路所存储的数字全部删除；
        while (count[a[j]] > 1)
        {
            count[a[i]] --;//慢指针当前所指的数字减一下
            i++;//慢指针走到下一位
        }
        ans = max(ans, j - i + 1);//更新最长区间
    }
    cout << ans;
    return 0;
}

快慢指针_应用场景_3

题意
给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。
请你判断 a 序列是否为 b 序列的子序列。
子序列指序列的一部分项按原有次序排列而得的序列，例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。
原题链接：https://www.acwing.com/problem/content/2818/
思路
设置一个快指针j和一个慢指针i，快指针j用来扫描大数组b，而慢指针则是读取小数组a的；
因为是按原有的次序截取的子序列，假如大数组是1 4 1 5 9 2 6，那子序列可以为4 5 2 6，但是不能为2 4 5 6；
所以可以设计j不断向后移动，而i只在匹配成功后才移动一位，当i等于a数组的元素个数时，说明匹配成功；
代码

#include<bits/std++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 0;i < n; i++) cin >> a[i];
    for(int i = 0;i < m; i++) cin >> b[i];

    //慢指针i读取小数组a
    int i = 0;
    //快数组j读取大数组b
    for(int j = 0;j < m; j++)
    {
        //如果i没读完a,并且子序列a中与b中的元素对应了，i往前走一格；
        if(i < n&&a[i] == b[j])  
                i++;
    }
    //如果子序列被完全读完，则a为b的子序列
    if(i == n) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

对撞指针_运用场景_1

一谈到对撞，第一个想到的肯定是二分，这里不再多说，详细看这里的讲解：https://www.cnblogs.com/RimekeyBergling/p/16395903.html

对撞指针_运用场景_2

题意
给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。
数组下标从 0 开始。
请你求出满足 A[i]+B[j]=x 的数对 (i,j)。
数据保证有唯一解。
原题链接https://www.acwing.com/problem/content/802/
思路
设置两个指针，一左一右，速度相同的i和j;
因为数组是升序；
所以i先读取，如果i + j > k , 则j往小数字方向走一格;
代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, k;
int a[N], b[N];
int main()
{
    cin >> n >> m >> k;
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int i = 0; i < m; i ++ ) cin >> b[i];
    //双指针，一左一右
    for (int i = 0, j = m - 1; i < n; i ++) 
    {
        //如果i + j > k , 则j往小数字方向走一格
        while(j >= 0 && a[i] + b[j] > k) j --;
        if(j >= 0 && a[i] + b[j] == k) cout << i << endl << j << endl;
    }
    return 0;
}

这篇关于双指针算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！