数组第二课，删除元素。
删除数组中的元素主要还是“覆盖”。这也是我第一次写双指针。
我的解法是使用头尾双指针，遇到要删除的元素就交换两个指针指向的元素。
Invariant：头指针之前的元素不含需要删除的值。
思路没问题，和题解一样是最优的一次遍历。但是写得太难看了：
def removeElement(self, nums: List[int], val: int) -> int:
tail = len(nums) - 1
for i in range(len(nums)):
if tail < i:
break
if nums[i] == val:
while nums[tail] == val:
tail -= 1
if tail < i:
return tail + 1
nums[i], nums[tail] = nums[tail], nums[i]
tail -= 1
return tail + 1
改进之后：
def removeElement(self, nums: List[int], val: int) -> int:
head = 0
tail = len(nums) - 1
while tail >= head:
if nums[head] == val:
nums[head] = nums[tail]
tail -= 1
else:
head += 1
return tail + 1
总结：双指针就不要用迭代器遍历了，画蛇添足。旧代码的while可以优化也可以不优化，时间是一样的。
两个指针从头开始。Invariant仍然是：头指针之前的元素不含需要删除的值。
def removeElement(self, nums: List[int], val: int) -> int:
left = 0
for right in range(len(nums)):
nums[left] = nums[right]
if nums[left] == val:
# 这个方法的精髓就是：写一句continue就相当于把nums[left]这个元素给删除了。
continue
left += 1
return left
这边因为快指针和迭代器的行为是一样的所以偷懒了。
思路和之前第二种双指针相同，判断条件变成了
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
left = 0
lastUniqueValue = nums[0]
for right in range(len(nums)):
nums[left] = nums[right]
if not left == 0 and nums[left] == lastUniqueValue:
continue
else:
lastUniqueValue = nums[left]
left += 1
return left
帽子戏法，这次的条件是碰到0就删。
def moveZeroes(self, nums: List[int]) -> None:
left = 0
for right in range(len(nums)):
nums[left] = nums[right]
if nums[left] == 0:
continue
left += 1
nums[left:] = [0] * (len(nums)-left)
最intuitive的解法是用栈。
双指针解法：竟然是反向双指针，无奈了。
通过观察，绝对值最大的在两头，所以头尾双指针。
特例：纯正数或者纯负数。这时只要让一边的指针动即可。
def sortedSquares(self, nums: List[int]) -> List[int]:
deque = collections.deque()
left = 0
right = len(nums) - 1
while left <= right:
sqleft = nums[left] ** 2
sqright = nums[right] ** 2
if sqleft >= sqright:
deque.appendleft(sqleft)
left += 1
else:
deque.appendleft(sqright)
right -= 1
return list(deque)
优化：一个好的deque的insertion应该是Amortized O(1)。当然因为本题中返回数组长度固定，也可以预先创一个数组然后追踪插入的index，这样就是纯纯的O(1)了。
前三例是删除元素，记住它们的解法。
后两例不算删除元素，但也是双指针。