提示1：本篇共包含5道题，全部用python语言进行实践，看会不如行动会，请大家多多实践～
提示2：强烈推荐 代码随想录
提示3：博主最近在跟着【代码随想录】进行刷题，有小伙伴有想法的可以私信博主，一起交流刷题心得！！！

系列文章

1. 代码随想录-数组篇01-二分查找
2. 代码随想录-数组篇02-双指针法

---

---

题目合集

本篇博客涉及的题目如下所示：

• 27. 移除元素
• 26. 删除有序数组中的重复项
• 283.移动零
• 844.比较含退格的字符串
• 977.有序数组的平方

---

一、双指针算法原理

  双指针法有两种形态：slow&fast以及left&right，其原理都是一样的。第一种形态从同一端出发，一个指针跑得快一个跑得慢；第二种形态从两端出发向中间靠拢。具体实现见下面的题目。

二、题目练习

Leetcode27. 移除元素

  ① 题目描述： 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
  ② 示例如下：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

  ③ 解题思路： 解决本题之前，需要了解一下数组的底层逻辑。删除数组中的一个元素并不是真正意义上的删除，物理空间上还是存在的，只是由于底层的计数器做了减减才使得返回的数据大小变小了。数组的删除是后面原始往前挪的一个覆盖操作，可以使用两层for循环进行暴力解决（这里不再给出代码），这里采用双指针法(快慢指针)是为了实现$O(n)$的算法复杂度，fast快指针代表新数组要放入的元素，slow慢指针代表新数组的下标。
  ④ 代码实现：

python">def removeElement(self, nums: List[int], val: int) -> int:slow = 0for fast in range(0, len(nums)):if nums[fast] != val:nums[slow] = nums[fast]slow += 1return slow

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

  ① 题目描述： 给你一个 非严格递增排列 的数组 nums，请你 原地 删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
  ② 示例如下：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

  ③ 解题思路： 双指针法（快慢指针），代码比较简单，希望大家手动模拟一下，以便于更好理解快慢指针的含义。

  ④ 代码实现：

python">def removeDuplicates(self, nums: List[int]) -> int:slow = 0for fast in range(0, len(nums)):if nums[fast] != nums[slow]:slow += 1# 维护 nums[0...slow]无重复元素nums[slow] = nums[fast]# 数组长度为索引 + 1return slow + 1

Leetcode283. 移动零

  ① 题目描述： 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。
  ② 示例如下：

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

  ③ 解题思路： 双指针法（快慢指针），强烈建议大家画图模拟一下指针的变化过程，有助于更好地理解。

  ④ 代码实现：

python">def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""if not nums:return -1slow = 0for fast in range(len(nums)):if nums[fast] != 0:nums[slow], nums[fast] = nums[fast], nums[slow]slow += 1# return slow/nums

Leetcode844. 比较含退格的字符串

  ① 题目描述： 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。注意：如果对空文本输入退格字符，文本继续为空。
  ② 示例如下：

输入：s = “ab#c”, t = “ad#c”
输出：true
解释：s 和 t 都会变成 “ac”。

  ③ 解题思路： 双指针思路，也可使用栈来模拟退格，这里只给出双指针思路，代码写的一般，欢迎大家指导调优。

  ④ 代码实现：

python">class Solution:def backspaceCompare(self, s: str, t: str) -> bool:new_S = self.delectstr(s)print(new_S)new_T = self.delectstr(t)if len(new_S) != len(new_T):return Falseelif new_S != new_T:return Falseelse:return Truedef delectstr(self, strs):# 将字符串转换为列表，因为字符串是不可变的s_list = list(strs)slow = 0for fast in range(0, len(s_list)):if s_list[fast] == "#":slow -= 1else:if slow < 0:slow = 0s_list[slow] = s_list[fast]slow += 1# 返回处理后的部分并转换为字符串return "".join(s_list[:slow])      

Leetcode977. 有序数组的平方

  ① 题目描述： 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
  ② 示例如下：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

  ③ 解题思路： 由于所给的数组是 非递减顺序 故数组的最大值只能在原始数组的两边产生，因此考虑使用双指针来解决该题目。
  ④ 代码实现：

python">def sortedSquares(self, nums: List[int]) -> List[int]:n = len(nums)i,j,k = 0,n - 1,n - 1ans = [-1] * nwhile i <= j:lm = nums[i] ** 2rm = nums[j] ** 2if lm > rm:ans[k] = lmi += 1else:ans[k] = rmj -= 1k -= 1return ans

---

总结

   双指针法有两种形态：slow&fast以及left&right，其原理都是一样的，这部分的题目具有迷惑性，希望大家多动手模拟，熟悉双指针所代表的含义。今天的题目就到这里了，下一篇我们继续刷！！！