双指针

双指针 #

1、数组 #

27. 移除元素 #

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

  • 删除数组里的元素，只能覆盖！

  • fast: 遇到对应元素就略过；遇到最终留下来的，赋值给slow.

  • slow: 这个坑是填最终要留下来的数的

26. 删除有序数组中的重复项 #

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

  • fast与slow.
  • 记得更新 val.

283. 移动零 #

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

  • fast：遇到0就略过；不是0就往前填 swap
  • slow

977. 有序数组的平方给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。 #

  • 平方的最大值就在数组的两端，不是最左边就是最右边。

  • 双指针法，i指向起始位置，j指向终止位置。

15. 三数之和 #

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

  • 排序
  • 三个指针指向三个位置：从左到右（for循环）、left、right（while循环）
  • 循环内：
    1. 条件判断（return）
    2. i 去重,注意[-1, -1, 2]
    3. left和right的去重,注意[0,0,0]

18. 四数之和 #

  • 不要判断 nums[k] > target 就返回了，如[-5, -4, -3, -1] -11

2、字符串 #

344. 反转字符串 #

编写一个函数，其作用是将输入的字符串反转过来。

  • left 和 right，移动，交换

844. 比较含退格的字符串 #

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。注意：如果对空文本输入退格字符，文本继续为空。

  • 退格影响的是#前面的那个字符！所以要从后往前遍历！

  • 两个字符串的指针指到的位置，一定是合法的字符

  • skipS和skipT的设置，这样指针才知道要删掉几个字符，该在哪里停下来。

  • 判断：要注意下标越界

    • 一定要先判断>=0，才去比较s[i]和t[j]

    • 指针指的位置一定是合法的，不是#，所以如果i和j有一个<0，一个不是，那一定不相等。

剑指 Offer 05. 替换空格 #

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

  • 先扩容数组resize：原size + 2*空格数量

  • 从后往前：很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

151. 翻转字符串里的单词给定一个字符串，逐个翻转字符串中的每个单词。 #

  • 移除多余的空格：即移除指定重复项。
    • 删除最前面的 = 把 fast指针移动到第一个非空格字符（因为后面会把 fast 的赋给 slow 的坑）
    • 双指针
    • 删除最后面的空格：slow 最后指向的有可能是：最后一个空格，或者合法字符。
  • 将整个字符串反转 + 将每个单词反转：用同一个reverse(left, right)函数

3、链表 #

206. 反转链表 #

反转一个单链表。

  • 解法一：递归
  • 解法二：三指针

24. 两两交换链表中的节点 #

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

  • 设dummy节点，模拟交换
    1. 新建虚拟头节点
    2. 模拟交换过程
    3. while循环条件：确保虚拟头节点（即前缀节点)+两个节点都不是空的
    4. 执行交换过程，不断设置和移动cur
    5. 返回值：dummy节点是不变的，返回其next就好

19. 删除链表的倒数第 N 个结点 #

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

  • 注意是先走n步，因为最终需要让slow走到要删除节点的前一个节点

02.07. 链表相交 #

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。

  • 如果相交了，则后面的节点必然都是相同的，所以：
    1. 先求出A的长度，再求出B的长度
    2. 让长的先走，走到剩下和短的一样
      • 小技巧：通过交换，让A变为长的
    3. 不断往后移，直到找到相等的。

142. 环形链表 II #

  • 判断链表是否有环？
    • 快慢指针一定会相遇，相遇的点就是在环内。因为相当于fast指针在追赶slow，且每次追赶1步。
  • 找到入口点？
    • 设x,y,z，fast走的路 = 2 * slow走的路，推导得出x和z的关系，来一遍同步指针不同点出发。