双指针法

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
慢指针：指向更新 新数组下标的位置
（右指针是快指针 right ，指向当前将要处理的元素，左指针left 是慢指针，指向下一个将要赋值的位置。）

• 时间复杂度：O(n)O(n)，其中 nn 为序列的长度。我们只需要遍历该序列至多两次。(其实是O(2n)
• 空间复杂度：O(1)O(1)。我们只需要常数的空间保存若干变量。

双指针的优化

优化原因

如果要移除的元素恰好在数组的开头，例如序列[1,2,3,4,5]，当val 为 1 时，我们需要把每一个元素都左移一位。注意到题目中说：「元素的顺序可以改变」。实际上我们可以直接将最后一个元素 5移动到序列开头，取代元素 1，得到序列[5,2,3,4]，同样满足题目要求。这个优化在序列中 val 元素的数量较少时非常有效。

优化方法

实现方面，我们依然使用双指针，两个指针初始时分别位于数组的首尾，向中间移动遍历该序列。

如果左指针left 指向的元素等于val，此时将右指针right 指向的元素复制到左指针left 的位置，然后右指针right 左移一位。如果赋值过来的元素恰好也等于val，可以继续把右指针right 指向的元素的值赋值过来（左指针left 指向的等于 val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于val 为止。

• 时间复杂度：O(n)O(n)，其中 nn 为序列的长度。我们只需要遍历该序列至多一次。
• 空间复杂度：O(1)O(1)。我们只需要常数的空间保存若干变量。

语法细节

1、python中

1. range 是生成一个列表，xrange用法与range完全相同，不同的是生成的不是一个list对象，而是一个生成器
2. 在生成很大的数字序列时候，用xrange会比range性能优很多，因为不需要一上来就开辟一块很大的内存空间
3. xrange和range都在循环的时候使用。
   2、解题一般是这样
   （1）注意：

		if not nums:return 0

这个不要丢！！
（2）left左指针，一般是进行交换或者覆盖完的操作之后，才移动。而右指针是一直移动的。
如：283移动零题目中：

        while right < len(nums):if nums[right] != 0:nums[left],nums[right] = nums[right],nums[left] # 满足某一条件，执行交换/覆盖操作left += 1 # 左指针在操作之后才移动right += 1 # 右指针无论有没有这个交换，一直移动

（3）整体思路：左指针左边都是已经处理好的内容，左指针指向的是将要处理（交换或者覆盖的内容），右指针是寻找满足条件的内容（跳过不满足条件的内容）来与左指针交换。左右指针之间是需要被替换，不满足题目要求的的元素（根据题目的意思，是要被移除的元素，或者需要被交换的0等等）
283、移动零中：
右指针i和左指针j的相对位置是：【已经处理好的数据】j【全是需要被交换的0】i【未处理的数据】。 然后i始终去找非0的数据进行交换，每次交换完，j的位置变成处理好的非0数据向后移动一个位置，等待i找到下一个需要交换的非0数据。（i，j指向的都不为0时，左右指针是同时向右移动的）
27、移除元素：
右指针i和左指针j的相对位置是：【已经处理好的数据】j【需要被移除的val】i【未处理的数据】
26、删除有序数组中的重复项
右指针i和左指针j的相对位置是：【已经处理好的数据】j【发生了重复，需要替换的元素】i【未处理的数据】