双指针-移除元素：
双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。 双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。
双指针力扣相关题目
27.移除元素
26.删除有序数组中的重复项
283.移动零
844.比较含退格的字符串
答案与解析：
27.移除元素
题目：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
解析：
因为不能使用额外空间，所以只能在原数组中进行修改得到输出数组，将要数值为val的元素放一起，将不数值不为val的元素放一起。可以使用双指针：快指针fast指向当前将要处理的元素，慢指针slow 指向下一个将要赋值的位置，并且只有当fast指针指向数值不为val的元素时，才将两个指针所在位置的元素进行替换。具体为：
指导处理完最后一个元素，此时已经将全部不为val的元素放入了输出数组，而slow指针所指的位置就是输出数组的长度。
python 代码：
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow=fast=0
while fast<len(nums):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
26.删除有序数组中的重复项
题目：给你一个升序排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
分析
由于不能使用额外空间，所以只能在元数组中修改，这就意味着可以使用双指针，fast指针负责指向要处理的元素，slow指针负责指向下一个不同元素要填入的下标位置。当数组为空数组时返回零，如果数组不是空数组，那么数组中至少包含一个元素，在删除重复元素之后也至少剩下一个元素，所以将两个指针分别从1位置开始。将fast指针遍历整个数组，如果nums[fast] != nums[fast-1]，说明nums[fast]和之前元素不同，因此把nums[fast]元素方到slow指针位置处，slow指针指向下一位置，同时fast指针继续遍历后面的元素。遍历结束后nums[0]到nums[slow-1]的每个元素都不相同且包含原数组中的每个不同的元素，因此新的长度即为 slow，返回slow 即可。
python 代码
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
fast = slow = 1
while fast < len(nums):
if nums[fast] != nums[fast-1]:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
283.移动零
题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
分析
因为题目要求必须在不复制数组的情况下原地对数组进行操作，所以只能在原数组上进行修改，可以使用双指针处理，fast指针负责遍历整个数组，slow负责指向下一个要放入不为0元素的位置，当fast指针处于非0元素时，将该元素放到slow指针处，并将slow指针处的元素放到faet指针处，slow指针指向下一位置，同时fast指针继续遍历后面的元素。
python 代码
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
fast=slow=0
while fast < len(nums):
if nums[fast] != 0:
nums[slow],nums[fast] = nums[fast],nums[slow]
slow += 1
fast += 1
return nums
844.比较含退格的字符串
题目：给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。#代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
分析
一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。
具体地，我们定义skip 表示当前待删除的字符的数量。每次我们遍历到一个字符：
这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。
python 代码
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
i, j = len(s)-1, len(t)-1
skipS, skipT= 0, 0
while i >= 0 or j >= 0:
while i >= 0:
if s[i] == '#':
skipS += 1
i -= 1
elif skipS > 0:
skipS -= 1
i -= 1
else:
break
while j >= 0:
if s[j] == '#':
skipT += 1
j -= 1
elif skipT > 0:
skipT -= 1
j -= 1
else:
break
if i >= 0 and j >= 0:
if s[i] != t[j]:
return False
elif i >= 0 or j >= 0:
return False
i -= 1
j -= 1
return True
977.有序数组的平方
题目：给你一个按非递减顺序 排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按 非递减顺序排序。
方法1
分析
因为数组是单增的，所以首先可以找到数组中负数与非负数的分界线neg，当数组每个元素平方后，0到neg单增，neg+1到n-1也单增，之后可以使用归并方法进行排序了，具体的，使用两个指针分别指向位置 neg 和 neg+1，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。当某一指针移至边界时，将另一指针还未遍历到的数依次放入答案。
python 代码
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
neg = -1
ans=list()
for i, num in enumerate(nums):
if num < 0:
neg = i
else:
break
方法2
分析
可以使用两个指针分别指向位置 0 和 n?1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况。
python 代码
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
i, j, pos = 0, n-1, n-1
ans=[0]*n
while i <= j:
if nums[i]*nums[i] > nums[j]*nums[j]:
ans[pos] = nums[i]*nums[i]
i += 1
else:
ans[pos] = nums[j]*nums[j]
j -= 1
pos -= 1
return ans
|