JS面试题寻找重复数

这几天遇到一个很有意思的面试题，我们一起看看

JS面试题寻找重复数

数组长度：n+1个整数

数字范围：1到n

绝对不能修改原数组（禁用排序等操作）

禁用常量级额外空间O(1)（常规哈希表操作堵死）

不能使用双层循环暴力破解法，会增加时间复杂度

其实很简单，我们可以想到使用链表方式

解题思路

1. 把数组当链表

2. 快慢指针追逐，找到环里的相遇点

   只要有环，快指针一定能追上慢指针

   就像两个人在操场跑步，快的一定会套圈慢的

3. 头指针 + 慢指针同步走 —— 找到环的入口

   从起点出发的指针，和从相遇点出发的慢指针，每次都走 1 步，最终一定在环的入口相遇！

答案：

let slow = 0, fast = 0;
const nums = [3, 1, 4, 2, 6, 7, 3];
console.log("遍历数组", nums);
console.log("======================================");

while (true) {
    console.log("【本轮开始】slow 位置：" + slow + "，值：" + nums[slow]);
    console.log("【本轮开始】fast 位置：" + fast + "，值：" + nums[fast]);

    // 慢指针走一步（先输出，再移动）
    slow = nums[slow];
    console.log("慢指针移动 → 新位置：" + slow + "，新值：" + nums[slow]);

    // 快指针走两步
    let step1 = nums[fast];
    fast = nums[step1];
    console.log("快指针移动 → 新位置：" + fast + "，新值：" + nums[fast]);

    console.log("--------------------------------------");

    if (slow === fast) {
        console.log("✅ 快慢指针相遇！位置：" + slow + "，值：" + nums[slow]);
        break;
    }
}

console.log("======================================");
let head = 0;
console.log("开始从头查找重复元素...");

while (head !== slow) {
    console.log("【本轮开始】head 位置：" + head + "，值：" + nums[head]);
    console.log("【本轮开始】slow 位置：" + slow + "，值：" + nums[slow]);

    // 头指针走一步
    head = nums[head];
    console.log("头指针移动 → 新位置：" + head + "，新值：" + nums[head]);

    // 慢指针走一步
    slow = nums[slow];
    console.log("慢指针移动 → 新位置：" + slow + "，新值：" + nums[slow]);

    console.log("--------------------------------------");
}

console.log("🎉 最终重复元素：" + slow);

输出结果：

遍历数组 [
  3, 1, 4, 2,
  6, 7, 3
]
======================================
【本轮开始】slow 位置：0，值：3
【本轮开始】fast 位置：0，值：3
慢指针移动 → 新位置：3，新值：2
快指针移动 → 新位置：2，新值：4
--------------------------------------
【本轮开始】slow 位置：3，值：2
【本轮开始】fast 位置：2，值：4
慢指针移动 → 新位置：2，新值：4
快指针移动 → 新位置：6，新值：3
--------------------------------------
【本轮开始】slow 位置：2，值：4
【本轮开始】fast 位置：6，值：3
慢指针移动 → 新位置：4，新值：6
快指针移动 → 新位置：2，新值：4
--------------------------------------
【本轮开始】slow 位置：4，值：6
【本轮开始】fast 位置：2，值：4
慢指针移动 → 新位置：6，新值：3
快指针移动 → 新位置：6，新值：3
--------------------------------------
✅ 快慢指针相遇！位置：6，值：3
======================================
开始从头查找重复元素...
【本轮开始】head 位置：0，值：3
【本轮开始】slow 位置：6，值：3
头指针移动 → 新位置：3，新值：2
慢指针移动 → 新位置：3，新值：2
--------------------------------------
🎉 最终重复元素：3

解析

指针位置：

slow指针：

因为指针6指向值3，使用指针3最终再次指向指针6，因此形成环

fast指针：

注意， fast 指针每次走两步是通过两次取值实现的

slow指针与fast指针相等，while循环跳出，循环结束

查找重复元素

新定义头指针，让头指针从0走一遍

slow指针，也跟着头指针走一遍（注意没有赋值为0，此时slow值为6）

初始指针状态：

循环指针过程：

头指针 == slow指针，因此值为3

广告：

• 高性能海外服务器低至200元/年