快慢指针与原地删除

快慢指针的模板是什么？

• slow 指向已处理区间的末尾, fast 指向当前待处理元素;
• fast 每轮右移一步, 满足条件时把元素写到 slow 位置并让 slow 前进;
• 结束时 slow 即为新数组长度;

slow = 0
fast = 0
while fast < len(nums):
    if 保留 nums[fast]:
        nums[slow] = nums[fast]
        slow += 1
    fast += 1

如何在有序数组中原地删除重复项？

• 首个元素一定保留, slow = 0, fast = 1;
• nums[slow] !== nums[fast] 时 slow 前进并写入 nums[fast];

function removeDuplicates(nums: number[]): number {
  let slow = 0;
  let fast = 1;
  while (fast < nums.length) {
    if (nums[slow] !== nums[fast]) {
      slow++;
      nums[slow] = nums[fast];
    }
    fast++;
  }
  return slow + 1;
}

• 时间复杂度: O(n); 空间复杂度: O(1);

如何原地移除指定元素或移动零？

• 移除元素: 保留条件为 nums[fast] !== val, 直接覆盖写入;
• 移动零: 保留条件为 nums[fast] !== 0, 用交换代替覆盖以保持非零元素的相对顺序;

function removeElement(nums: number[], val: number): number {
  let left = 0;
  let right = 0;
  while (right < nums.length) {
    if (nums[right] !== val) nums[left++] = nums[right];
    right++;
  }
  return left;
}

function moveZeroes(nums: number[]): void {
  let slow = 0;
  let fast = 0;
  while (fast < nums.length) {
    if (nums[fast] !== 0) {
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      slow++;
    }
    fast++;
  }
}

如何原地压缩字符串？

• slow 指向压缩后的写入位置, fast 指向当前字符;
• 先用 start 记录当前字符的起点, 向右跳过所有相同字符;
• 写入字符本身;
• 数量大于 1 时把数量的十进制字符逐位写入;
• 返回 slow 即压缩后长度;

function compress(chars: string[]): number {
  let slow = 0;
  let fast = 0;
  while (fast < chars.length) {
    const start = fast;
    while (fast + 1 < chars.length && chars[fast] === chars[fast + 1]) fast++;
    chars[slow++] = chars[start];

    const count = fast - start + 1;
    if (count > 1) {
      for (const ch of String(count)) chars[slow++] = ch;
    }
    fast++;
  }
  return slow;
}

快慢指针还能解决什么？

• 调整数组顺序: 把满足某性质的元素移到前部 (如奇数在前), 只需替换保留条件;
• 链表问题: 判环、找中点、找倒数第 k 个节点;