什么是双指针？

双指针顾名思义就是两个指针，是一个算法思想。但双指针往往是值某几种类型的双指针，而不是仅仅就指两个指针。一般在遍历对象的过程中，使用两个相同方向（快慢指针）或者相反的方向（左右指针）的指针进行遍历。快慢指针和左右端点指针一般是解决双指针一类题的解决方法。
以下对左右指针常见问题的套路总结

左右指针的常见算法和套路

左右端点指针也称碰撞指针，最左侧的索引定义为左指针（left），最右侧的定义为右指针（right），两个指针分别从两头开始向中间进行数组遍历，互相碰面后遍历结束。

图解：

套用公式：

1
2
3
4
5
6
7
8
9
10
11
const fn = (list:number[]) => {
	let left = 0;
	let right = list.length - 1;
	// 遍历数组
	while(left <= right) {
		left++;
		// 一些条件判断和处理
		... ...
		right++；
	}
}

这一般常用来解决的问题：

主要是解决数组或者是字符串中的问题。（例如：移除数组元素，翻转字符串数组，二分查找）

例子：

例1:双指针翻转字符串

1
2
3
4
5
6
7
8
9
10
11
12
const reverseString = (s: string[]): void => {
  let left = 0;
  let right = s.length - 1;
  while (left <= right) {
    if (s[left] !== s[right]) {
      [s[left], s[right]] = [s[right], s[left]];
    }
    left++;
    right--;
  }
  console.log('s:', s);
};

例2: 移除数组元素 给定一个数组 一个val 原地移除数组里等于val的值 返回移除后数组的长度(双指针思想)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const removeElement = (nums: number[], val: number): number => {
  let left = 0;
  let last = nums.length - 1;
  while (left <= last) {
    if (nums[left] === val) {
      nums[left] = nums[last];
      nums.splice(last, 1);
      last--;
    } else {
      left++;
    }
  }
  console.log(nums);
  return left;
};

例3:两个有序数组的合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const merge2 = (nums1: number[], nums2: number[], m: number, n: number): void => {
  let p = m + n - 1; // p初始值指向 nums1长度为m+n后的数组 最后一位
  let p1 = m - 1; // p1指向nums1原数组的最后一位
  let p2 = n - 1; // p2指向nums2数组的最后一位
  // 空数组判断： 如果p1 或p2其中有一个<0 则 有一个是空数组 则直接就把nums2插入到nums1就可以了
  if (p1 < 0 || p2 < 0) {
    nums1.splice(0, n, ...nums2);
  }
  // p2 指针越界后循环结束
  while (p2 >= 0) {
    // 将nums1[p1]和nums2[p2]的值相比较
    // 大的一方 赋值给nums1[p] p每一次循环都往前移动，p1和p2指针根据谁指的值大 谁往前移一位
    if (nums2[p2] < nums1[p1]) {
      nums1[p] = nums1[p1];
      p--;
      p1--;
    } else {
      nums1[p] = nums2[p2];
      p--;
      p2--;
    }
  }
  console.log('merge2——nums1:', nums1);
};

例4:二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const binarySearch = (nums: number[], target: number): number => {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = left + (right - left);
    if (target > nums[mid]) {
      left = mid + 1;
    } else if (target < nums[mid]) {
      right = mid - 1;
    } else return mid;
  }
  return -1;
};
binarySearch([-1, 0, 3, 5, 9, 12], 9) //输出4
binarySearch([-1, 0, 3, 5, 9, 12], 1) //输出-1

双指针之左右指针题的gitHub地址：

https://github.com/Sugar-MM/AlgorithmPractice/tree/main/src/doublePointer