简介

  • 剑指Offer 书籍阅读笔记

双指针

  • 双指针是一种常用的解题思路，可以使用两个相反方向或者相同方向的指针扫描数组从而达到解题目的。

  • 指针，并不专指C语言中的指针，而是一个相对宽泛的概念，是能定位数据容器中某个数据的手段。在数组中它实际上是数字的下标

  • 方向相反的双指针经常用来求排序数组中的两个数字之和。一个指针P1指向数组的第一个数字，另一个指针P2指向数组的最后一个数字，然后比较两个指针指向的数字之和及一个目标值。如果两个指针指向的数字之和大于目标值，则向左移动指针P2；如果两个指针指向的数字之和小于目标值，则向右移动指针P1。此时，两个指针的移动方向是相反的。

  • 方向相同的双指针，通常用来求正数数组中子数组的和或者乘积。初始化的时候两个指针P1和P2都指向数组的第一个数字。如果两个指针之间的子数组的和或成绩大于目标值，则向右移动指针P1删除子数组最左边的数字；如果两个指针之间的子数组的和或乘积小于目标值，则向右移动指针P2在子数组的右边增加新的数字。此时两个指针的移动方向是相同的

  • 双指针，是解决与数组相关的面试题的一种常用技术。如果数组是排序的，那么应用双指针技术就能够用O(n)的时间在数组中找出两个和为给定值的数字。
  • 如果数组中的所有数字都是整数，那么应用双指针技术就可以用O(1)的辅助空间找出和为给定值的子数组

双指针 链表

  • 所谓双指针是指利用两个指着来解决与链表相关的面试题，这是一种常用思路。双指针思路又可以根据两个指针不同的移动方式细分为两种不同的方法。

  • 第一种方法是前后双指针，即一个指针在链表中提前朝着指向下一个节点的指针移动若干步，然后移动第二个指针。
    • 前后双指针的经典应用是查找链表的倒数第K个节点。先让第1个指针从链表的头结点开始朝着下一个节点的指针先移动K - 1步，然后让第二个指针指向链表的头节点，在让两个指针以相同的速度一起移动，当第一个指针达到链表的尾节点时，第二个指针正好指向倒数第K个节点
  • 第二种方法是快慢双指针，即两个指针在链表中移动的速度不一样，通常是快的指针朝着下一个节点的指针一次移动两步，慢的指针一次只移动一步。
    • 采用这种方法，在一个没有环的链表中，当块的指针到达链表尾节点的时候慢的指针正好指向链表的中间节点