一、算法描述

双指针，常用于处理数组类型的数据，通过俩个指针来指向不位置所代表的值也可以是相同位置的数值。

二、算法实质

双指针，通过操作俩个指针的指向来完成对于数据的处理。

三、算法思想

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

过程图解：

image-20230803122447583

四、快慢指针使用条件

  • 在一个序列里边，用两个指针维护一段区间
  • 在两个序列里边，一个指针指向其中一个序列，另外一个指针指向另外一个序列，来维护某种次序

五、案例

  • 删除排序数组中的重复项

    • 题目 链接:https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

      给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

    • 判题标准

      系统会用下面的代码来测试你的题解:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      int[] nums = [...]; // 输入数组
      int[] expectedNums = [...]; // 长度正确的期望答案

      int k = removeDuplicates(nums); // 调用

      assert k == expectedNums.length;
      for (int i = 0; i < k; i++) {
          assert nums[i] == expectedNums[i];
      }

      如果所有断言都通过，那么您的题解将被 通过。

    • 算法思路

      • 第一种情况 给定数组num长度为0 || 1不包含任何元素 直接返回0 || 1
      • 第二种情况 在删除重复元素后至少剩下一个元素 保留nums[0] 删除后续元素
      • 第三种情况，当nums大于0且删除重复元素后仍有其他元素，则定义两个指针一个快指针 fast 一个慢指针 slow，快指针标识遍历数组到达的下标位置，慢指针标识下一个不同元素要填入的下标位置，初始时两个指针都指向下标1，假设数组nums的长度为n，将快指针fast一次遍历从1到n-1的位置，对于每个位置如果nums[fast] != nums[fast-1] 说明nums[fast]和之前的元素都不同，因此将nums[fast]的值复制到nums[slow]，然后将slow的值+1即为指向下一个位置。遍历结束之后从nums[0]到nums[slow-1]的每个元素都不相同且包含原数组中的每个不同元素，因此新的长度即为slow返回slow即可。

    • 官方代码

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      class Solution {
          public int removeDuplicates(int[] nums) {
              int n = nums.length;
              if (n == 0) {
                  return 0;
              }
              int fast = 1, slow = 1;
              while (fast < n) {
                  if (nums[fast] != nums[fast - 1]) {
                      nums[slow] = nums[fast];
                      ++slow;
                  }
                  ++fast;
              }
              return slow;
          }
      }

    • 复杂度

      • 时间复杂度:O(n)，其中n为数组的长度。快慢指针最多各移动n次
      • 空间复杂度:O(1)，只需要使用常数额外空间

六、个人见解

  • 个人解题代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution {
        public int removeDuplicates(int[] nums) {
            int result = 1;
            if(nums.length == 1) return result;
            for (int i = 0; i < nums.length; i++) {
                for (int j = i + 1; j < nums.length; j++) {
                    if (nums[i] != nums[j]) {
                        nums[result] = nums[j];
                        i = j - 1;
                        result++;
                        break;
                    }
                }
            }
            if (result != nums.length) {
                for (int i = result; i < nums.length; i++) {
                    nums[i] = -1;
                }
            }
            return result;
        }
    }

  • 个人解题见解

    个人采用的是暴力解法，每次遍历到与该数值不相同的就进行交换，交换的位置为result的长度，每次交换后将i的数值等于j-1的位置继续开始，枚举出所有的情况，将所有不重复升序的数值提前，最后处理特别情况，如果result的长度不等于nums的长度就将后续值全部替换为-1等于是排除数组中全是1出现n+1次的情况。

  • 对于快慢指针的见解

    采用双指针的方式，可以很直观的解决数组中此类的问题，慢指针为条件下的位置，快指针通常为遍历数组寻找特定条件，当快指针越界时候为结束的条件。