leetcode 双指针算法专题
一、什么叫做双指针算法？
双指针是一种方法，一种思想一种技巧，也谈不上什么特别的算法，在二分查找中经常使用这个技巧，具体就是用两个变量动态的存储两个或者多个的结点，来方便我们进行一些操作，通常使用在线性结构中，比如说数组或者是链表。 在我们遇到像数组，链表这类数据结构的算法题目的时候，应该要想得到双指针的来解决问题。特别是链表类的题目，经常需要用到两个或多个指针配合来记忆链表上的节点，完成某些操作。链表这种数据结构也是树形结构和图的原型，所以有时候在关于图和树形结构的算法题目中也会用到双指针。
1、快慢指针
1）计算链表的中点：快慢指针从头节点出发，每轮迭代中，快指针向前移动两个节点，慢指针向前移动一个节点，最终当快指针到达终点的时候，慢指针刚好在中间的节点。 2）判断链表是否有环：如果链表中存在环，则在链表上不断前进的指针会一直在环里绕圈子，且不能知道链表是否有环。使用快慢指针，当链表中存在环时，两个指针最终会在环中相遇。 3）判断链表中环的起点：当我们判断出链表中存在环，并且知道了两个指针相遇的节点，我们可以让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。 4）求链表中环的长度：只要相遇后一个不动，另一个前进直到相遇算一下走了多少步就好了 5）求链表倒数第k个元素：先让其中一个指针向前走k步，接着两个指针以同样的速度一起向前进，直到前面的指针走到尽头了，则后面的指针即为倒数第k个元素。（严格来说应该叫先后指针而非快慢指针）
2、碰撞指针
一般都是排好序的数组，否则无序的话这两个指针的位置也没有什么意义。特别注意两个指针的循环条件在循环体中的变化，小心右指针跑到左指针左边去了。常用来解决的问题有
1）加粗样式二分查找问题 2）n数之和问题：比如两数之和问题，先对数组排序然后左右指针找到满足条件的两个数。如果是三数问题就转化为一个数和另外两个数的两数问题。以此类推。 3）反转数组
3、滑动窗口法
两个指针，一前一后组成滑动窗口，并计算滑动窗口中的元素的问题。
这类问题一般包括 1）字符串匹配问题 2）子数组问题
二、具体相关leetcode习题
1) leetcode 1. 两数之和
这个题目比较简单，不需要用到双指针，一般在用双指针的时候，需要有序数组，先排序。这题目有几种思路，首先我想到的就是利用暴力方法，直接算。看代码：
嵌套循环 -> 第二层为什么是i+1开始呢？因为比如说题目中的例子（0号位置和1号位置分别是2和7相加等于9满足条件，那么从i=1开始遍历的时候，j就不能从0开始了，不然就重复了，所以从i的下一位开始遍历）
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i]+nums[j]==target:
return i,j双指针的方法如下： 首先对这个数组先进行一次拷贝 然后对拷贝的数组进行排序 定义两个指针，一个指向首部，一个指向尾部 现在就开始利用双指针的方法对该数组进行遍历，条件是（i<j） 如果找到了 两个数字 加上 等于 target的值的 就结束while循环 下一步就是 对找到的这个数字 对他 在原数组 也就是nums里面 进行索引值的查找 最后返回找到的这两个数字在原数组中的 索引
在这里要注意的一点就是 想要利用双指针进行遍历 前提是对这个数组进行排序 python中的sort（）方法
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
temp=nums.copy()
temp.sort()
i=0
j=len(nums)-1
while i<j:
if (temp[i]+temp[j])>target:
j=j-1
elif (temp[i]+temp[j])<target:
i=i+1
else:
break
p=nums.index(temp[i])
print(nums.pop(p))
k=nums.index(temp[j])
if k>=p:
k=k+1
return [p,k]2）leetcode 167. 两数之和 II - 输入有序数组
这个题目和leetcode 1 略微有点不同，这题给你的条件就是这个数组就是已经排序了的数组，所以对于原数组，不需要进行排序，也就是说对原来的数组不需要跟leetcode 1一样，先进行数组的拷贝，在进行排序，算法思路如下： 其实代码也比较好理解，这里就不解释了…依旧是双指针，首尾往中间遍历
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
if not numbers:
return []
#利用双指针
#首指针
i = 0
high = len(numbers)-1
#开始进行循环
while i<=high:
if numbers[i] + numbers[high] == target:
return [i+1,high+1]
if numbers[i] + numbers[high] > target:
high-=1
if numbers[i] + numbers[high] < target:
i +=1
return[-1,-1]3）leetcode 633. 平方数之和
对于这道题，依旧是利用双指针的方法去结题，观察题目，问你是否存在两个数等于某个定值，和上一道题相比，也类似，只是这道题多了平方。 定义首尾指针，往中间靠拢，尾部的数字最好是定义为c的开根号，如果为c的开根号，那么正好等于和正好等于c嘛！ 然后就是类似于上两题的双指针遍历了啊
class Solution(object):
def judgeSquareSum(self, c):
"""
:type c: int
:rtype: bool
"""
i = 0
j = int(c**0.5)
while i<=j:
if i**2+j**2==c:
return True
if i**2+j**2>c:
j-=1
if i**2+j**2<c:
i+=1
return False4）leetcode 26. 删除排序数组中的重复项
这里用到了先后指针，和快慢指针区别开来（容易混淆）用一段动画解释这个算法吧…哈哈哈 1、起初，爸爸和儿子都在起点上，爸爸先走一步…让儿子拿着篮子在原地先等候…
2、老爸向前走一步，发现和第一次一样，又是草莓，就没搭理继续向前走
3、现在找到的是哈密瓜，诶，和之前的不一样了，让儿子向前走一步，把哈密瓜给了儿子…
4、老爸又向前走一步，是哈密瓜和之前的一样，没有捡，再往前一步，还是哈密瓜，还是不敢捡，那就再走一步… 5、老爸继续往前走，看到了西瓜，心里乐开花，赶紧让儿子向前一步，把西瓜给了儿子…
以下是代码部分：
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
#运用快慢指针
slow = 0
for i in range(1,len(nums)):
if nums[slow] != nums[i]:
slow+=1
nums[slow]=nums[i]
return slow+15）leetcode 345. 反转字符串中的元音字母
一开始看到这个题目的时候，题目其实我都没看懂，其实也就是意思说从前面走，从后面走，只要遇到了元音字母就将这两个字母调换，题目还考虑了一个隐含的条件，那就是大写字母不要忘记啦！！ 还要注意的就是python中一些特定的API函数的用法…
代码解释：
先将字符串转成列表
定义首尾指针进行遍历
最后一个API函数："".join(string) 将列表转成字符串
class Solution(object):
def reverseVowels(self, s):
"""
:type s: str
:rtype: str
"""
if (len(s)==0):
return ""
if (len(s)==1):
return s
yuanyin = "aeiou"
string = list(s)
# print(string)
i = 0
j = len(string)-1
while i<j:
if string[i].lower() not in yuanyin:
i+=1
if string[j].lower() not in yuanyin:
j-=1
if string[i].lower() in yuanyin and string[j].lower() in yuanyin:
string[i],string[j] = string[j],string[i]
i+=1
j-=1
return "".join(string)6）leetcode 125. 验证回文串
这个题目，只考虑字母和数字字符，要求我们要知道一个API函数 isalnum() 返回值是True 或者 False
我的思路是先将这个字符串转成纯数字或者字母的形式：
result = "".join(ch.lower() for ch in s if ch.isalnum())
再利用双指针收尾进行遍历
其中lower()是将大写字母转成小写
当遍历当两个指针对应的位置，不相等时，直接返回False ,如果相等，首指针加一，尾指针减一，继续判断条件，直到循环结束…这一题还是比较简单的
import re
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
if(len(s)==0):
return True
if(len(s)==1):
return True
result = "".join(ch.lower() for ch in s if ch.isalnum())
# print(result)
# List = list(result)
# print(List)
i = 0
j = len(result) - 1
print(j)
while i<j:
if result[i].lower() != result[j].lower():
return False
i+=1
j-=1
return True7）leetcode 680. 验证回文字符串 Ⅱ
这个题目相比于上一道题难度要大一点，因为要判断改字符串是不是回文字符串，如果不是，删掉一个字符还是不是回文字符串，如果是，那就是，哈哈哈…
其实看了代码思路也比较简单了，先写一个函数判断这个字符串是不是回文字符串check(left, right)
双指针进行首尾遍历，如果相等，首指针加一，尾指针减一，继续判断
如果不相等，将首指针加一，尾指针不变 或者 首指针不变，尾指针减一 ， 来进行判断
check(left + 1, right) or check(left, right - 1)
class Solution(object):
def validPalindrome(self, s):
def check(left, right):
# 判断是否是回文数
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
# 定义指针，一个指向开始，一个指向末尾
left, right = 0, len(s) - 1
while left < right:
# 指针所对应的字符相同时，指针往中间移动
if s[left] == s[right]:
left += 1
right -= 1
# 指针所对应的字符不同，考虑删除一个字符
# 1. 删除当前左指针的字符，移动至后一位
# 2. 删除当前右指针的字符，移动至前一位
# 重新判断删除字符后，字符串是否是回文字符串
else:
return check(left + 1, right) or check(left, right - 1)
return True8）leetcode 88. 合并两个有序数组
反正其中有一种方法很简答，一行代码搞定…
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: None Do not return anything, modify nums1 in-place instead.
"""
nums1[:] = sorted(nums1[:m]+nums2)这种方法就是：先创建一个空的列表 然后一个指针对nums1进行遍历 一个指针对nums2进行遍历，去比较他们的大小 谁小，谁就放到temp中，然后指针记得移位置 如果nums1已经遍历完了，那么就把nums2的元素append进temp中 如果nums2已经遍历完了，那么就把nums1的元素append进temp中 最后将temp数组 赋值 给 nums1数组
class Solution(object):
def merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: None Do not return anything, modify nums1 in-place instead.
"""
temp = []
# print(temp)
p1 = 0
p2 = 0
while p1 <m and p2 <n:
if nums1[p1]<nums2[p2]:
temp.append(nums1[p1])
p1+=1
else:
temp.append(nums2[p2])
p2+=1
while p1<m:
temp.append(nums1[p1])
p1+=1
while p2<n:
temp.append(nums2[p2])
p2+=1
nums1[:] = temp[:]9）leetcode 977. 有序数组的平方
创建一个全为0长度为n的列表 双指针进行首尾遍历 如果前面的平方大于后面的平方，那么就把前面的值加入到创建的列表中，然后这个数字较大的指针加一，以此类推
class Solution(object):
def sortedSquares(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
#用双指针的做法
#定义一个空的列表
n = len(nums)
temp = [0]*n
#双指针
i,j,pos = 0,n-1,n-1
while i<=j and pos >=0:
if nums[i]*nums[i] > nums[j]*nums[j]:
temp[pos] = nums[i]*nums[i]
i+=1
else:
temp[pos] = nums[j]*nums[j]
j-=1
pos-=1
return temp10） leetcode 141. 环形链表
这个时候就用到了快慢指针的方法，一个指针走一格，另一个指针走两格，如果两个指针相等，那么证明一定有环！
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
#依然是快慢指针的解法
fast , slow = head , head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False11）leetcode 142. 环形链表 II
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow,fast = head,head
while True:
#如果列表的尾部会为空
if not (fast and fast.next):
return
slow = slow.next
fast = fast.next.next
if fast == slow:
break
fast = head
while fast!=slow:
slow = slow.next
fast = fast.next
return fast腾讯云开发者
