今日复习了数组部分，对以下题目做了一个整理。
27. 移除元素

这里将不再详细讲述两层for循环的暴力算法。其大致思路是：第一层for循环遍历每一个元素，找到值为val的元素之后，从该位置将每一个元素往前移动一位进行覆盖；整体数组长度减1。

解下来主要讲解两种方法：

方法1：

使用替换的方法，直接将等于val的元素（我们记为ele）用数组末尾元素nums[length]进行替代，然后将数组长度length减去1。这里需要注意的是代替元素ele的末尾元素nums[length]不一定不等于val，所以需要再检测一次，即i -= 1。

class Solution:def removeElement(self, nums: List[int], val: int) -> int:length = len(nums) - 1 i = 0while i <= length:if nums[i] == val:nums[i] = nums[length]length -= 1i -= 1i += 1return length + 1

方法2

使用双指针方法求解，双指针在算法题里面非常常见，例如，在本人整理快速排序的时候就有使用到双指针。这里也可以使用相同的思路，将pre作为边界，左边是需要的元素，右边是不确定的元素。cur指针负责找需要的元素，这里是nums[cur] != val。

class Solution:def removeElement(self, nums: List[int], val: int) -> int:pre = -1cur = pre + 1length = len(nums)while cur <= len(nums) - 1:if nums[cur] != val:pre += 1nums[pre] = nums[cur]else:length -= 1cur += 1return length

双指针解决数组问题的相似题目

我们寻找相似的题目： 26. 删除有序数组中的重复项，使用双指针方法解决。

class Solution:def removeDuplicates(self, nums: List[int]) -> int:pre = 0cur = 1length = len(nums)while cur <= len(nums) - 1:if nums[pre] != nums[cur]:pre += 1nums[pre] = nums[cur]else:length -= 1cur += 1return length

也可以不使用length来记录数组长度，因为之前提到pre可以看成是有效数组的边界值，所以这里也可以直接返回pre + 1，来作为长度。

同理，283. 移动零，其解决方法如下：

class Solution:def moveZeroes(self, nums: List[int]) -> None:"""Do not return anything, modify nums in-place instead."""pre = -1 cur = 0while cur <= len(nums) - 1:if nums[cur] != 0:pre += 1nums[pre], nums[cur] = nums[cur], nums[pre]#cur += 1

在 977. 有序数组的平方 中，我们也可以使用双指针：

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:result = []left = 0right = len(nums) - 1while left <= right: #squaredleft = pow(nums[left], 2)squaredright = pow(nums[right], 2)if squaredleft >= squaredright:result.insert(0, squaredleft)left += 1else:result.insert(0, squaredright)right -= 1return result

这里，我们设置了新的数组result进行返回，由于数组是递增序列，我们这里设置了两个指针分别指向原先数组的头left尾right。因为当原数组元素有正有负时，平方后两端元素大于中间元素。当然，我们也可以找出原来元素中最接近0的元素位置（平方后的最小值），然后从它开始向两端移动。