【算法入坑】（一）双指针yyds，学完双指针刷题贼爽嘞

💖比起被围观，悄悄努力或许更踏实💖

系列文章目录🍁

文章目录

🌴前言

大家好，我是小沐！😃编程路上一个人可能走的更快，但一群人才能走得更远，关注小沐一起学习不迷路！今天分享的是双指针的用法，后续还会有leetcode上的相关题目。话不多说，秃头走起——>冲冲冲👊👊👊！！！

🌿一、基础知识

首先要注意，此指针非彼指针。双指针算法中的指针是索引（如数组下标）而不是C/C++中的指针。

上面字符串的索引范围为[0,11]
双指针即双索引，对于同一数组或字符串有两个索引。

🌿二、分类及应用

注：在例子中我们以 i , j 或 left , rigth 表示两个指针。

1.普通双指针

两个指针往同一个方向移动。

例题：Leetcode第27题：移除元素 原题链接

思路：
①起始令i，j 都指向下标为0处；
②如果 j 指针指向的值不等于 val，它一定是输出数组的一个元素，我们就将 j 指针指向的值复制到 i 指针位置，然后将两个指针同时右移；
③如果 j 指针指向的元素等于 val，它不能在输出数组里，此时 i 指针不动，j 指针右移一位。

代码如下：

intremoveElement(int* nums,int numsSize,int val){int i=0;for(int j=0;j<numsSize;j++){if(nums[j]!=val){
            nums[i]=nums[j];++i;}}return i;}

上述算法的时间复杂度为O(n),但由于最差情况下遍历了两次数组，时间开销还是比较大的。

2.对撞双指针

两个指针面对面移动。

例题：Leetcode第27题：移除元素 原题链接

思路：
①起始令left指向数组下标为0处，令right指向数组下标为n-1处；
②如果左指针指向的值不等于目标值，左指针向右移动一步；
③如果左指针指向的值等于目标值，用右指针指向的值覆盖掉左指针指向的值，并让右指针向左移动一步。
④设置结束条件，确定遍历到每一个元素的同时不重复遍历。

代码如下：

intremoveElement(int* nums,int numsSize,int val){int n=numsSize;int left=0;for(int right=n-1;left<=right;){if(nums[left]!=val)++left;else{
            nums[left]=nums[right];
            right--;}}return left;}

这种算法只需遍历一次数组，时间复杂度为O(n).值得一提的是，这种方法往往要求数组是有序排列的。

3.快慢双指针

一个为快指针，一个为慢指针。 下面是一道很经典的例题。

LeetCode第141题：环形链表 原题链接

思路：
①我们定义两个指针，一快一满。慢指针slow每次只移动一步，而快指针fast每次移动两步;
②初始时，慢指针在位置 head，而快指针在位置 head.next；
③这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(structListNode* head){if(head ==NULL|| head->next ==NULL){return false;}structListNode* slow = head;structListNode* fast = head->next;while(slow != fast){if(fast ==NULL|| fast->next ==NULL){return false;}
        slow = slow->next;
        fast = fast->next->next;}return true;}

💫三、思维拓展

1.三指针？四指针？

学完了三指针，那么有没有三指针甚至四指针呢？答案是肯定的，鉴于目前小沐需要刷刷双指针的题目来加以巩固，以后有时间了，可以去尝试看看有没有多指针的题目参考，大家可以先关注小沐，不迷路哈哈！

2.刷LeetCode

🌴总结

今日分享到此结束👊👊👊，由于笔者还在求学之路上辗转徘徊🏃，水平有限，文章中可能有不对之处，还请各位大佬指正🙏，祝愿每一个热爱编程的人都能实现追求，考研上岸进大厂，熬夜秃头卷中王。最后欢迎关注小沐，学习路上不迷路！😜

注：以上题目转自Leetcode.