avatar
文章
98
标签
61
分类
17
主页
存档
标签
分类
友情链接
关于作者
BaiDing's blog
主页
存档
标签
分类
友情链接
关于作者
算法系列之双指针法
|算法
字数总计:3.3k|阅读时长: 11 分钟
|阅读量:|评论数:

双指针法

    所谓双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向或者相反方向的指针进行扫描，从而达到相应的目的。


1、对撞指针

    对撞指针是指在有序数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。

    对撞数组适用于有序数组，也就是说当你遇到题目给定有序数组时，应该第一时间想到用对撞指针解题。

1） 求和问题

    对于这种问题，常见的算法思路不外乎遍历，回溯，但这里，双指针遍历法是一个很有效的方法。具体思路是：初始化两个指针，一个指向数组的第一个元素，另外一个指向数组的最后一个元素，在两个指针相遇之前，指针1只能向前移动，指针2 只能向后移动。比较当前两个指针所指元素和与给定数字的大小，如果和较大，指针2向后移动，如果和较小，指针1向前移动。最终的结果是找到两个满足条件的数或者不存在这样的两个数字。

1

A. 两数之和问题

leetcode链接—题1

问题

给定一个整数数组nums，返回数组中两个数之和为目标值target的两个整数的下标

思路

  • 对数组进行排序
  • 初始化两个指针，一个指向头L，一个指向尾R
  • 判断nums[L] + nums[R] 与 target 的关系
  • 若nums[L] + nums[R] > target，则说明nums[R]比较大，故R—。若nums[L] + nums[R] < target，则说明nums[L]比较小，故L++。
  • 直到L>R结束
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def twoSum(nums: List[int], target: int) -> List[int]:
    nums.sort()
    L = 0
    R = len(nums) - 1
    while(L < R):
        if nums[L] + nums[R] > target:
            R -= 1
        elif nums[L] + nums[R] < target:
            L -= 1
        else:
            break

    if L < R:
        return [L, R]
    else:
        return None


B. 三数之和问题

leetcode链接—题15

问题

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

思路

  • 对数组进行排序
  • 首先按照顺序选择第一个数字nums[i]，之后利用双指针法得到之后的两个数字
  • 遍历排序后数组：
    • 若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
    • 对于重复元素：跳过，避免出现重复解
    • 令左指针 L=i+1，右指针 R=n-1，当 L<R 时，执行循环：
      • 当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R移到下一位置，寻找新的解
      • 若和大于 0，说明 nums[R]太大，R左移
      • 若和小于 0，说明 nums[L]太小，L右移
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def threeSum(nums: List[int]) -> List[List[int]]:
    nums.sort()
    l=len(nums)
    result = []
    if(l<3):
        return result
    for i in range(l):
        if nums[i]>0:                         ##如果值大于0，则加和肯定大于0，返回
            return result                
        if(i>0 and nums[i]==nums[i-1]):       ##对于重复元素，跳过
            continue    
        L=i+1
        R=l-1
        while(L<R):
            if(nums[i]+nums[L]+nums[R]==0):      
                result.append([nums[i],nums[L],nums[R]])
                while(L<R and nums[L]==nums[L+1]):   #对于左边有相同元素，省略
                    L+=1
                while(L<R and nums[R]==nums[R-1]):   #对于右边有相同元素，省略
                    R-=1
                L+=1
                R-=1
            elif(nums[i]+nums[L]+nums[R]>0):		#nums[R]偏大时
                R-=1
            else:
                L+=1
 	return result


C. 最接近的三数之和

leetcode链接—题16

问题

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

思路

该题的思路与三数之和几乎一致，只是这次是进行比较

  • 对数组进行排序
  • 首先按照顺序选择第一个数字nums[i]，之后利用双指针法得到之后的两个数字
  • 使用res记录答案
  • 遍历排序后数组：
    • 令左指针 L=i+1，右指针 R=n-1，当 L<R 时，执行循环：
      • 令tmp=nums[i]+nums[R]+nums[L]
      • 若abs(tmp-target) < abs(res-target)，说明我们找到了更有的结果，替换res
      • 若 tmp == target，说明，该结果最合适，最直接返回
      • 若tmp>target，说明nums[R]太大，要让其变小，才有可能找到最适合的结果，R左移
      • 若tmp<target，说明nums[L]太小，要让其变大，才有可能找到最适合的结果，L右移
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def threeSumClosest(nums: List[int], target: int) -> int:
    nums.sort()
    l = len(nums)
    res=float('inf')
    for i in range(l):
        L = i+1
        R = l-1
        while(L<R):
            tmp = nums[i]+nums[R]+nums[L]
            if(abs(tmp-target) < abs(res-target)):
                res=tmp
            if(tmp==target):
                return tmp
            elif(tmp>target):
                R-=1
            else:
                L+=1
   return res


D. 四数之和

leetcode链接—题18

问题

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

思路

与三数之和问题一致，只是将外层遍历改成两层，此处不放代码了。


2）盛最多水的容器

leetcode链接—题11

问题

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

思路

  • 设S(i,j)为i与j之间的水的面积，h(i)表示第i个点的高度，res代表面积最大的值
  • 定义左指针为L=0，右指针R=n-1
  • 每次将L，R中较小的一个往里面移动，计算面积，更新res，直到L>R结束

PS：该思路的难点在于，该解法是都一定将所有的情况都遍历到

  • 我们从(0,n-1)开始计算，如果h(0)比较小，那么易知，S(0,j) (其中0<j<n-1)都小于S(0,n-1)，有了这个知识，我们就可以进行如下的描述
  • 如果将所有的面积值，列成一个矩阵(n+1行，n+1列），行代表左边，列代表右边
  • 如果h(0)比较小，就让我们将0这一行的情况，都知道了，即这一行的最大值为(0,n-1)这个点，这一行的其他地方，我们就不需要再遍历了。之后，就到了下一行的(1,n-1)。如果是h(n-1)较小，那么在n-1这一列的情况就知道了。
  • 于是，我们可以知道我们的算法是一列一列的或者一行一行的来排除情况
  • 我们总共遍历n+1次，因此，可以将所有的面积值都考虑到
1
2
3
4
5
6
7
8
9
10
11
12
13
def maxArea(height: List[int]) -> int:
        i=0
        j = len(height)-1
        result = 0
        while(i<j):
            tmp = min(height[i],height[j])*(j-i)
            if tmp > result:
                result =tmp
            if(height[i]<height[j]):
                i+=1
            else:
                j-=1
        return result

3）快速排序法类方法

此类方法，使用了双指针，从两侧进行遍历数组，一旦两个元素符合条件，则进行交换，来达到目的

A. 快速排序

快速排数采用了双指针的思想，时间复杂度为$ O(nlog_2n)$ 。

问题

对数组nums进行排序

思路

  • 首先选择数组nums[0]为基准，假设值为H，置左指针L=1，右指针R=n-1
  • 右侧先进行移动，找到第一个小于H的值，之后左侧进行移动，找到第一个大于H的值，将两个值进行交换。
  • 交换完成后，R，L继续这样移动，直到L==R，将H与nums[L]交换。首先移动右侧是为了在L等于R的位置上是小于H的数。
  • 交换完成后，在H的左侧都是小于H的数字，右侧都是大于H的数字
  • 再分别对H的左侧和H的右侧进行快速排序，即可得到最后的结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def quick_sort(nums: List[int],left:int,right:int)-> List[int]:
    if left>=right:				
        return
    key=nums[left]				#设左边第一个数为基准数
    L=left					    #设定左指针
    R=right						#设定右指针
    while(L!=R):
        while(nums[j]>=key and L<R):	#右指针开始往左走，直到找到一个大于key的值
            R-=1
        while(nums[i]<=key and L<R):	#左指针开始往右走，直到找到一个小于key的值
            L+=1
        if(L<R):						#如果L<R，交换那两个找到的值
            t=nums[L]
            nums[L]=nums[R]
            nums[R]=t
    nums[left]=nums[L]						#将基准数与最后停下来的数进行交换
    nums[L]=key
    quick_sort(nums,left,L-1)			#对左边的数进行快速排序
    quick_sort(nums,L+1,right)			#对右边的数进行快速排序


B. 奇偶排序

问题

给定一个数组，数组中元素有奇数有偶数。要求对数组进行处理，使得数组的左边为奇数，右边为偶数

思路

奇偶排序与快速排序的方法类似，只是将快速排序的条件更改成了奇数和偶数的不同



2、快慢指针

    快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如fast每次增长两个，slow每次增长一个。

1）链表中点问题

    对于单链表求中间元素的问题，经典的作法是采用两个指针，初始化都指向链表表头，移动开始时，快指针移动两步，慢指针移动一步。当快指针的next为null或者快指针为null的时候，慢指针所指的就是单链表的中间元素(注意奇数个元素和偶数个元素的处理)

2）删除链表的倒数第N个节点

leetcode链接—题19

问题

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

思路

高阶方法：我们可以通过两个指针，依次遍历来找到倒数第N个节点，一个快节点，一个慢节点，慢节点比快节点慢n+1步，当第一个节点遍历完后，第二个节点指向的就是倒数第N+1个节点

  • 初始化两个指针，fast，slow 都指向头
  • 使用fast指针从头遍历链表，使用i记录快指针的步数
  • 当i达到临界值，即当i>n时，表示fast比slow多走了n+1步了，这个时候slow指针也开始移动
  • 直到遍历结束，此时slow指针指向倒数第N+1个节点，i记录了链表的总长度
  • 删除第N个节点即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
        if(head.next is None):		#如果只有1个节点，直接返回None
            return None
        fast=head					#快指针
        slow=head					#慢指针
        i=0							#记录快指针的位置
        while(fast):
            fast=fast.next			#快指针移动
            if(i>n):				#当快指针比慢指针快n+1步时
                slow = slow.next	#慢指针移动
            i+=1
        if(i==n):					#如果删除的是第一个元素，更换返回的头部
            return head.next
        slow.next = slow.next.next
        return head


3）删除排序数组中的重复项

leetcode链接—题26

问题

给定一个有序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

思路

  • 既然不能使用额外的数组空间，那么我们就将不同的元素依次放到数组前面去
  • 初始化两个指针，快指针fast和慢指针slow
  • fast元素用来找到指针中的不同元素，slow指针用来将这些不同元素放到特定位置
  • 遍历一遍数组即可
1
2
3
4
5
6
7
def removeDuplicates(nums: List[int]) -> int:
    slow=0
    for fast in range(len(nums)):
        if(nums[fast] != nums[slow]):    #如果出现不同的元素
            slow += 1					 #将slow指针加1，将其更改为不同的元素
            nums[slow]=nums[fast]
    return slow+1		#返回不同元素的数目

参考链接

文章作者: 白丁
文章链接: http://baidinghub.github.io/2020/04/03/%E7%AE%97%E6%B3%95%E7%B3%BB%E5%88%97%E4%B9%8B%E5%8F%8C%E6%8C%87%E9%92%88%E6%B3%95/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 BaiDing's blog！
算法双指针法
打赏
  • 微信
    微信
  • 支付寶
    支付寶
相关推荐
2020-04-03
算法系列之动态规划（一）基础DP
2020-04-03
算法系列之十大排序算法
2020-04-03
算法系列之贪心法
2020-04-03
算法系列之广度优先搜索
2020-04-03
算法系列之深度优先搜索
评论
繁