双指针从简单到复杂

283. 移动零

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

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

方案1

一个简单直接的方法就是把所有的非零元素过滤出来，然后放到一个新的数组中

class Solution:def moveZeroes(self, nums: List[int]) -> None:res = []for val in nums:if val != 0:res.append(val)return res

方案2

但是要求不是使用新的数组，只能在原来的数组中操作。一个简单直接的方法就是遍历数组，找到第一个为0的值，然后接着往后遍历找到第一个不为0的值，把这个非0值填充到0值的位置。

然后进行交换，把非零值放到前面去

然后接着再找到一个非0值放到前面的0去

接着再交换，把非零值放到0的位置

修修补补总算是完成了第一版

class Solution:def moveZeroes(self, nums: List[int]) -> None:zero_index = 0no_zero_index = 0while zero_index < len(nums) and no_zero_index < len(nums):# 1. 找到第一个0值，如果为不为0则继续查找while zero_index < len(nums) and nums[zero_index] != 0:zero_index += 1no_zero_index = zero_index + 1# 2. 找到0后面第一个非0值，如果为0则继续查找while no_zero_index < len(nums) and nums[no_zero_index] == 0:no_zero_index += 1if zero_index < len(nums) and no_zero_index < len(nums):# 3. 把非0和0值进行交换，也就是把非0值挪到前面去nums[no_zero_index],nums[zero_index] = nums[zero_index],nums[no_zero_index]return nums[:zero_index]

方案3

看了一下题解的双指针思路，真的是不太能想出来。

class Solution:def moveZeroes(self, nums: List[int]) -> None:# 1. 定义双指针slow = fast = 0while fast < len(nums):# 2. 找到非0值if nums[fast] != 0:# 3. 将非0值和0值进行交换nums[slow],nums[fast] = nums[fast],nums[slow]# 4. slow往后移动一步slow += 1# fast往后移动一步fast += 1return nums[:slow]

fast不断移动找到非0值

然后进行交换，slow后移一位

fast接着找非0值，然后再次进行交换，不断重复

思考

核心思想就是，快指针不断遍历，找到符合条件的位置，然后将这个位置的值放的慢指针的地方（交换或覆盖），慢指针移动到下一个位置，等待被替换。

这里面有一个点让我非常纠结，为什么慢指针只会移动一个位置，怎么就保证下个位置就一定OK的呢？例如这个例子中，快指针不断遍历找到非0的位置，但是怎么就保证慢指针的位置的值就一定是0呢？做几个简单的例子

fast和slow上来就不为0，

fast上来就是符合条件的值，进行处理，fast和slow进行交换（自己跟自己）

然后slow的位置后移

fast接着不断遍历找到非0值

进行处理，fast和slow进行交换（自己跟自己）

然后slow的位置后移

fast接着不断遍历找到非0值

整个流程好像也没有问题。

核心逻辑就是，当fast和slow的位置一致的时候，其实是没有任何处理的，

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

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

• 快指针找不重复的元素，如果这个元素与慢指针位置相同，则不断往后，如果不同，说明找到了一个不重复的元素，slow后移一位，覆盖这个位置

slow前为已经处理过的元素，即已经都是非重复元素，slow和fast之间是无需处理的元素，

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

用两个指针（快指针和慢指针）遍历数组，通过快指针筛选出不等于目标值的元素，并用慢指针记录已经处理好的元素位置。相当于把所有 “有用” 的元素（不等于val的）依次 “搬运” 到数组的前面，而慢指针的位置正好对应新数组的长度。

• 慢指针 slow 始终指向新数组的下一个空位（等待被填充有效元素）
• 快指针 fast 负责 “探路”，找到所有需要保留的元素
• 当 fast 找到有效元素时，就把它 “送” 到 slow 指向的空位，然后 slow 向前挪一位（下一个空位）

class Solution:def removeElement(self, nums: List[int], val: int) -> int:slow = fast = 0while fast < len(nums):# 1. 快指针筛选出不等于目标值的元素if nums[fast] != val:# 2. 把快指针的值放到等待被填充的位置，即slownums[slow] = nums[fast]# 3. 移动慢指针，等待下一个填充slow += 1fast += 1return slow