双指针

双指针就是用两个变量维护两个位置，让它们按规则移动。

同向双指针

两个指针都从左往右走。快指针负责遍历，慢指针维护答案位置。

适合原地删除、去重、压缩数组。

let slow = 0

for (let fast = 0; fast < nums.length; fast++) {
  if (满足保留条件) {
    nums[slow] = nums[fast]
    slow++
  }
}

27. 移除元素

function removeElement(nums: number[], val: number): number {
  let slow = 0

  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== val) {
      nums[slow] = nums[fast]
      slow++
    }
  }

  return slow
}

对撞双指针

一个指针从左边走，一个指针从右边走，每次排除一边。

适合有序数组、两端收缩、找最大面积。

let left = 0
let right = nums.length - 1

while (left < right) {
  if (满足条件) {
    left++
  } else {
    right--
  }
}

11. 盛最多水的容器

面积由短板决定，所以每次移动更短的一边。

function maxArea(height: number[]): number {
  let left = 0
  let right = height.length - 1
  let res = 0

  while (left < right) {
    const h = Math.min(height[left], height[right])
    res = Math.max(res, h * (right - left))

    if (height[left] < height[right]) {
      left++
    } else {
      right--
    }
  }

  return res
}

167. 两数之和 II

数组有序，和小了左指针右移，和大了右指针左移。

function twoSum(numbers: number[], target: number): number[] {
  let left = 0
  let right = numbers.length - 1

  while (left < right) {
    const sum = numbers[left] + numbers[right]

    if (sum === target) return [left + 1, right + 1]
    if (sum < target) {
      left++
    } else {
      right--
    }
  }

  return []
}

分离双指针

两个指针分别在两个数组上移动。

适合合并两个有序数组、判断子序列。

let i = 0
let j = 0

while (i < arr1.length && j < arr2.length) {
  if (条件1) {
    i++
  } else if (条件2) {
    j++
  } else {
    i++
    j++
  }
}

392. 判断子序列

i 走 s，j 走 t。匹配上了，i 才往后走。

function isSubsequence(s: string, t: string): boolean {
  let i = 0
  let j = 0

  while (i < s.length && j < t.length) {
    if (s[i] === t[j]) {
      i++
    }
    j++
  }

  return i === s.length
}