26. 删除有序数组中的重复项

双指针 1

使用两个指针表示区间，然后遍历完所有的元素

function removeDuplicates(nums: number[]): number {
  // 记录相同元素的区间
  let left = 0 // 左区间
  let right = 1 // 右区间
  let k = 0 // 不重复元素的长度

  // 遍历完所有的 nums
  while (left < nums.length) {
    // 先找到所有相同元素的区间
    while (nums[left] === nums[right]) {
      right += 1
    }

    // 更新 k 所在的位置的值
    nums[k] = nums[left]

    // 进行下一次处理
    // 更新 k
    k += 1

    // 更新区间
    left = right
    right = left + 1

  }

  return k
}

双指针 2

和上面思路一样，但是其实不需要额外记录 K

function removeDuplicates(nums: number[]): number {
  // 快慢指针所在的值应该是一样的
  // 如果遇到不一样的，说明进入新的区间了
  let slow = 0 // 慢指针，表示当前最后一个不重复值开始位置
  let fast = 1 // 快指针 ，表示当前重复区间的最后一个位置

  // 遍历完所有的 nums
  while (fast < nums.length) {
    // 出现不同元素
    // 处理下个区间
    if (nums[slow] !== nums[fast]) {
      // 更新 slow 位置和值
      slow += 1 // slow 前进一位
      nums[slow] = nums[fast] // 更新 slow 所在位置
    }

    // 无论是否相同， fast 都要去看下一个
    fast += 1
  }

  // slow 所在的位置就是最后一个不重复元素
  // 因为 slow 是 index，所以 len 需要 + 1
  return slow + 1
}

双指针 3

和上面思路一样，不过比较的是 right - 1 和 right

这样不用将 slow 和 right 设置为一致，只需要 right 开始新的区间的时候更新 slow 最终的值即可

区别就是这次在切换区间的时候更新的是上一个区间的 slow

function removeDuplicates(nums: number[]): number {
  if (!nums.length) {
    return 0
  }

  // 快慢指针所在的值应该是一样的
  // 如果遇到不一样的，说明进入新的区间了
  // slow 最少为 1，所以从 1 开始处理即可
  let slow = 1 // 慢指针，表示如果出现新的区间，应该在哪个位置赋值
  let fast = 1 // 快指针 ，表示当前重复区间的最后一个位置

  // 遍历完所有的 nums
  while (fast < nums.length) {
    // 出现不同元素
    // 处理当前区间
    if (nums[fast - 1] !== nums[fast]) {
      nums[slow] = nums[fast] // 更新 slow 的值
      slow += 1 // slow 前进一位，指向下个区间的开始
    }

    // 无论是否相同， fast 都要去看下一个
    fast += 1
  }

  // slow 的值就是 index
  // 因为每次出现新区间都是先赋值，这样保证了赋值是正确的
  // 紧接着再 + 1，保证 len 也改为正确的了
  return slow
}