双指针法

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。

也就是在一个数组上，使用2个指针来同时遍历数组，此时的遍历的时间复杂度为O(n)。

  1. function fn (list) {
  2.   var left = 0;
  3.   var right = list.length - 1;
  5.   //遍历数组
  6.   while (left <= right) {
  7.     left++;
  8.     // 一些条件判断 和处理
  9.     ... ...
  10.     right--;
  11.   }
  12. }

以经典题为例：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 双指针法 - 图1#card=math&code=O%281%29&id=Z5Grv) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。你不需要考虑数组中超出新长度后面的元素。力扣链接

示例 1: 给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

暴力解题

很明显暴力解法的时间复杂度是双指针法 - 图2#card=math&code=O%28n%5E2%29&id=D5U7O)，这道题目暴力解法在leetcode上是可以过的。

  1. // 时间复杂度：O(n^2)
  2. // 空间复杂度：O(1)
  3. class Solution {
  4. public:
  5.     int removeElement(vector<int>& nums, int val) {
  6.         int size = nums.size();
  7.         for (int i = 0; i < size; i++) {
  8.             if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
  9.                 for (int j = i + 1; j < size; j++) {
  10.                     nums[j - 1] = nums[j];
  11.                 }
  12.                 i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
  13.                 size--; // 此时数组的大小-1
  14.             }
  15.         }
  16.         return size;
  18.     }
  19. };
  • 时间复杂度：双指针法 - 图3#card=math&code=O%28n%5E2%29&id=LEFW4)
  • 空间复杂度：双指针法 - 图4#card=math&code=O%281%29&id=KqMOl)

双指针法

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

  1. class Solution {
  2.     public int removeElement(int[] nums, int val) {
  3.         int index = 0;
  4.         for(int i = 0; i < nums.length; i++) {
  5.             if(nums[i] != val) {
  6.                 nums[index++] = nums[i];
  7.             }
  8.         }
  9.         return index;
  10.     }
  11. }
  • 时间复杂度：双指针法 - 图5#card=math&code=O%28n%29&id=O6cTW)
  • 空间复杂度：双指针法 - 图6#card=math&code=O%281%29&id=wp0hV)

相关题目

删除排序数组中的重复项

题目描述（力扣链接）

双指针法 - 图7

解题方法：

相等直接赋值给上一个指针，但注意 i 从第一个开始，所以第一个应该首先加进去

  1.     class Solution {
  2.         public int removeDuplicates(int[] nums) {
  3.             int slowIndex = 0;
  4.             int i = 1;
  5.             while (i < nums.length) {
  6.                 if (nums[slowIndex] == nums[i]) {
  7.                     i++;
  8.                 } else {
  9.                     // 此处为++slowIndex，因为第一个需要加进去
  10.                     nums[++slowIndex] = nums[i];
  11.                 }
  12.             }
  13.             // 此处返回的是长度
  14.             return slowIndex + 1;
  15.         }
  16.     }

移除零

题目描述（力扣链接）

双指针法 - 图8

解题方法：

双指针法直接得出答案

  1. class Solution {
  2.     public void moveZeroes(int[] nums) {
  3.         int index = 0;
  4.         for(int i = 0; i < nums.length; i++) {
  5.             if(nums[i] != 0){
  6.                 nums[index++] = nums[i];
  7.             }
  8.         }
  9.         // 后面依次赋0即可
  10.         for(;index < nums.length; index++) {
  11.             nums[index] = 0;
  12.         }
  13.     }
  14. }

比较含退格的字符串

题目描述（力扣链接）

双指针法 - 图9

解题方法：

先转化为数组，非 ’#‘ 直接将值赋值到上一个指针，如果为 ’#‘ 则将指针减一，下次赋值就会覆盖，最后截取开始到指针得字符数组。

  1. class Solution {
  2.     public boolean backspaceCompare(String s, String t) {
  3.         return change(s).equals(change(t));
  4.     }
  6.     public static String change(String s) {
  7.         int index = 0;
  8.         // 先转化为数组
  9.         char[] chars = s.toCharArray();
  10.         for (int i = 0; i < chars.length; i++) {
  11.             // 如果不为#则赋值
  12.             if (chars[i] != '#') {
  13.                 chars[index++] = chars[i];
  14.             }
  15.             // 如果为#号，且index在不在第一个位置则进行回退
  16.             else if(chars[i] == '#' && index != 0) {
  17.                 index--;
  18.             }
  19.         }
  20.         // 注意截取，并转化为字符串
  21.         return String.valueOf(chars,0,index);
  22.     }
  23. }

有序数组的平方

题目描述（力扣链接）

双指针法 - 图10

解题方法：

方法一：

直接将所有树平方，再排序，此时时间复杂度是 双指针法 - 图11#card=math&code=O%28n%20%2B%20n%5Clog%20n%29&id=Psw33)

  1. class Solution {
  2.     public int[] sortedSquares(int[] nums) {
  3.          // 解法一
  4.          int index = 0;
  5.          for (int i = 0; i < nums.length; i++) {
  6.              nums[index++] = nums[i] * nums[i];
  7.          }
  8.          // 使用sort自动排序
  9.          Arrays.sort(nums);
  10.          return nums;
  11.     }
  12. }

方法二:

双指针法，时间复杂度为O（n）。

此时数组左右两边分别使用left和right指针进行平方判断，大得数字在新数组中倒序赋值 。（详细解法）

  1. class Solution {
  2.     public int[] sortedSquares(int[] nums) {   
  3.         // 双指针解法二
  4.         int index = nums.length - 1, left = 0, right = nums.length - 1;
  5.         int[] result = new int[nums.length];
  6.         while (left <= right) {
  7.             if (nums[left] * nums[left] > nums[right] * nums[right]) {
  8.                 result[index--] = nums[left] * nums[left];
  9.                 left++;
  10.             }else {
  11.                 result[index--] = nums[right] * nums[right];
  12.                 right--;
  13.             }
  14.         }
  15.         return result;
  16.     }
  17. }

两个数字上的双指针法

两个数组的交集 II
https://www.yuque.com/jugelizi-rxt6d/dqbihl/nam035
见题一