前言

（1）简介

首先明确一下，这里的指针并非C或C++中的指针，从名字容易产生误解，这只是一种算法思想，也不是一种数据结构。

这里的指针准确的说其实就是索引，回想在数组遍历的时候，经常会写for循环，用一个指针来记录当前遍历的项(arrays[ i ])。那么双指针实际上就是有两个这样的指针

一般可以分为左右指针，快慢指针，和固定间距指针(滑动窗口中常见，文章链接）

（2）应用场景
数组，字符串，链表等

数组和字符串：前后指针较多，快慢指针也有
链表：快慢指针（因为链表没有索引，不容易得到尾指针）

个人感觉，快慢指针要比前后指针难一点，技巧更多点

左右指针

两个指针相向而行或者相背而行

1.lc125 验证回文串

lc125 链接

描述：

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串

示例：

输入: s = “A man, a plan, a canal: Panama”
输出：true

Solution：
回文串是一个经典问题。验证方法很多，比如双指针，API（reverse），栈等

这里讲一下前两种

简单又暴力的API如下（空间复杂度较高）

 public boolean isPalindrome(String s) {String s1 = s.replaceAll("[^A-Za-z0-9]","").toLowerCase();StringBuilder sb = new StringBuilder(s1);return sb.reverse().toString().equals(s1) ;
}

双指针如下

public boolean isPalindrome(String s) {int left=0, right = s.length()-1; // 双指针while(left<right){while(left<right && !Character.isLetterOrDigit(s.charAt(left)))left++;while(left<right && !Character.isLetterOrDigit(s.charAt(right)))right--;if(Character.toLowerCase(s.charAt(left))!=Character.toLowerCase(s.charAt(right)))return false;left++;right--;     }return true;}

当然还可以开辟一个String或StringBuilder类，这样处理更方便些（缺点当然是费空间）

最后，可以看一下 lc9 链接 也是回文串，不同的是给的输入是数字。第一种解法就是直接转化为字符串（熟悉Java API的使用），但是费空间；第二种就是对数字本身处理，这就不属于双指针的内容了。

2.lc5 最长回文子串

lc5 链接

描述：

给你一个字符串 s，找到 s 中最长的回文子串

示例：

输入：s = “babad”
输出：“bab”（“aba” 同样是符合题意）

Solution：
左右指针，相背而行！利用中心拓展法，从中间开始，然后往两边双指针

    int left=0,right=0;int maxLen=0;public String longestPalindrome(String s) {int len = s.length();for(int i=0;i<s.length();i++){longestPallindrome(s,i,i,len); // 以i为中心longestPallindrome(s,i,i+1,len);  // 以i+1为中心}return s.substring(left,right+1);      }public void longestPallindrome(String s,int i,int j,int len){while(i>=0 && j<len && s.charAt(i)==s.charAt(j)){if(j-i+1>maxLen){left = i;right = j;   maxLen = j-i+1; }i--;j++;}}

还可以用动态规划！

3. lc344 反转字符串

LeetCode字符串 文章中有介绍，比较简单，这里就不说了

快慢指针

两个指针同向而行，一快一慢（即两个指针步长不同）

1. lc26 删除有序数组中的重复项

lc26链接

描述：

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致

示例：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]

Solution:

 public int removeDuplicates(int[] nums) {int slow = 0;for(int fast=1;fast<nums.length;fast++){if(nums[fast]!=nums[slow]){slow++;nums[slow] = nums[fast];  }}return slow+1;}

2. lc83 删除排序链表中的重复元素

lc83链接

此题与上一题几乎一样（就是把数组改成链表）
Solution:

public ListNode deleteDuplicates(ListNode head) {if(head==null )return null;ListNode slow=head,fast=head.next;while(fast!=null){if(fast.val !=slow.val){slow.next = fast;slow = slow.next;}fast = fast.next;}slow.next = null;return head;}

3. lc27 移除元素

简单说就是给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素

之前文章有过 见题解

4. lc19 删除链表的倒数第N个节点

描述：

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

示例：

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

Solution：
链表中的文章介绍过，可以说是个固定间距的双指针

public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1,head);ListNode slow=dummy,fast = dummy;for(int i=0;i<n+1;i++){fast = fast.next;}while(fast!=null){slow = slow.next;fast = fast.next;}slow.next = slow.next.next;return dummy.next;}

5. lc142 环形链表 II

lc142链接

描述：

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

示例：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点

Solution：
先判断链表中是否有环（快慢指针相遇），相遇后在用两个指针分别指向头指针和此时相遇的，再同时出发，相遇点即为环入口。（Floyd 判圈算法）

public ListNode detectCycle(ListNode head) {ListNode fast = head,slow = head;while(fast!=null && fast.next!=null){fast = fast.next.next;slow = slow.next;if(slow==fast){     ListNode index1 = head,index2 = slow;while(index1 != index2){index1 = index1.next;index2 = index2.next;}return index1;}            }return null;          }

6. lc287 寻找重复数

描述：

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。 假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例：

输入：nums = [1,3,4,2,2] 输出：2

Solution：
看到重复第一反应HashSet，但是题目要求O(1)——利用上题的环形链表

public int findDuplicate(int[] nums) {int slow=0,fast=0;while(true){          slow =nums[slow] ;fast = nums[nums[fast]];if(nums[slow]==nums[fast]){int index=0;while(nums[index]!=nums[slow]){index = nums[index];slow = nums[slow];}return nums[index];}}return 0;}

固定间距指针

见 滑动窗口这篇文章，滑动窗口用到其实就是固定间距指针和快慢指针

双指针+排序

（待定）