Knowledge_Repository

主题

Teeker2026-04-06
1092
4.2m

快慢指针高频题型模板整理 ​

好的，这就为你整理一份快慢指针高频题型模板，包含解题思路、核心代码和关键要点，你可以直接套用。

🚀 快慢指针高频题型模板 ​

1. 移除元素（原地移除指定值） ​

题目：给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

核心思路：快指针找有效元素，慢指针存有效元素。

JavaScript

function removeElement(nums, val) {
  let slow = 0;
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== val) {
      nums[slow] = nums[fast]; // 搬运有效元素
      slow++;
    }
  }
  return slow; // 新数组长度
}

✅ 关键要点：

  • 不需要额外数组，原地修改，空间复杂度 O(1)。

  • slow 既是新数组的长度，也是下一个有效元素的存放位置。

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

题目：给你一个升序排列的数组 nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。

核心思路：快指针遍历，慢指针记录不重复元素的位置。

JavaScript

function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let slow = 0;
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast]; // 搬运不重复元素
    }
  }
  return slow + 1; // 新数组长度（slow从0开始）
}

✅ 关键要点：

  • 数组是升序的，所以重复元素一定相邻。

  • slow 初始为 0，从第二个元素开始比较。

3. 寻找链表的中间节点 ​

题目：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

核心思路：快指针走两步，慢指针走一步，快指针到终点时，慢指针正好在中间。

JavaScript

function middleNode(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

✅ 关键要点：

  • 时间复杂度 O(n)，只需要一次遍历。

  • 无需计算链表长度，适合处理未知长度的链表。

4. 环形链表检测 ​

题目：给定一个链表的头节点 head，判断链表中是否有环。

核心思路：快指针每次走两步，慢指针每次走一步。如果有环，快慢指针一定会相遇；如果无环，快指针会先到终点。

JavaScript

function hasCycle(head) {
  if (head === null || head.next === null) return false;
  let slow = head;
  let fast = head.next;
  while (slow !== fast) {
    if (fast === null || fast.next === null) return false;
    slow = slow.next;
    fast = fast.next.next;
  }
  return true;
}

✅ 关键要点：

  • 空间复杂度 O(1)，无需额外哈希表。

  • 初始时 fast 领先一步，避免一开始就相遇。

5. 有序数组的平方 ​

题目：给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

核心思路：数组平方后最大值一定在两端，用双指针从两端向中间遍历，把较大的平方值放到结果数组的末尾。

JavaScript

function sortedSquares(nums) {
  const n = nums.length;
  const res = new Array(n);
  let slow = 0;
  let fast = n - 1;
  let index = n - 1;
  while (slow <= fast) {
    const left = nums[slow] * nums[slow];
    const right = nums[fast] * nums[fast];
    if (left > right) {
      res[index] = left;
      slow++;
    } else {
      res[index] = right;
      fast--;
    }
    index--;
  }
  return res;
}

✅ 关键要点：

  • 时间复杂度 O(n)，避免了先平方再排序的 O(n log n) 复杂度。

  • 双指针从两端向中间收敛，用 index 从后往前填充结果数组。

💡 快慢指针核心思想总结 ​

  1. 原地修改数组：用慢指针记录有效位置，快指针寻找有效元素，搬运覆盖实现 O(1) 空间。

  2. 链表问题：快指针速度是慢指针的 2 倍，可快速定位中间节点或检测环。

  3. 两端收敛：处理有序数组的平方、两数之和等问题，从两端向中间遍历。

  4. 时间复杂度：大部分题型时间复杂度为 O(n)，只需要一次遍历。

如果你需要，我可以帮你把这些模板整理成一个可运行的 JavaScript 文件，包含所有题型的完整代码和测试用例，你可以直接复制到本地运行验证。需要吗？

（注：文档部分内容可能由 AI 生成）

最近更新