企业官网建设流程全解析

刷LeetCode热题100的时候，有一道题让我的印象格外深：第287题，寻找重复数。不是因为它难到让人崩溃，恰恰相反——在数组里找重复数字，这事简单得像入门题。把数组排个序，或者塞进HashSet里数一遍，五分钟写完。可等你提交的时候会发现，题目里那行小字才是真正的考点：不能修改数组，只能使用O(1)额外空间。就这一行，把“一把梭”的解法全部拦在门外。

这道题在Java面试里出现频率相当高，尤其大厂算法面。它考的不只是你会不会遍历，而是你对二分查找、快慢指针、位运算这些基础工具的理解深度，以及对题目约束条件的敏感度。这篇文章想把这道题从头到尾拆一遍：题目到底在说什么、每种解法背后的原理、Java实现里的边界细节、面试官会怎么追问，最后再说说“找重复”这件事在真实项目里的投影。不管你是准备面试的Java选手，还是单纯刷题打基础，应该都能从中拿到点东西。

1. 读懂限制条件：这题为什么不能“一把梭”

1.1 题目到底在说什么：n+1个苹果放进n个抽屉

先看原题描述：给定一个包含 n + 1 个整数的数组 nums，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有一个重复的整数，返回这个重复的数。你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

这里最关键的设定是“n + 1 个位置，但元素值只有 n 种可能”。用鸽巢原理（抽屉原理）一想就明白：n 个抽屉，塞 n + 1 个球，必然至少有一个抽屉里有两个球。换句话说，重复的存在性是由数据范围天然保证的，不需要任何额外证明。题目还给了更强的约束：只有一个重复的整数。注意措辞是“只有一个重复的整数”，不是“只有一个元素重复”。比如数组 [1, 2, 3, 2, 2]，重复整数是 2，它出现了三次，但重复的数值只有一个。我们要找的是这个值，而不是它的出现次数。

这个细节非常重要。很多人一上来就写一个“找到出现两次的元素”的解法，但题目要的是“出现至少两次的那个值”。如果重复数出现三次、四次，你的计数器逻辑会直接崩掉。

1.2 两条限制把常规解法全毙了

题目末尾那句限制是这道题真正的灵魂：“必须不修改数组 nums 且只用常量级 O(1) 的额外空间。”这两条规则不是随便写的，它们精确地封死了三个最直观的方案。

第一个被封死的是排序法。把数组排个序，重复的数必然相邻，一趟扫描就能找到：

Arrays.sort(nums); for (int i = 1; i < nums.length; i++) { if (nums[i] == nums[i - 1]) { return nums[i]; } }

这段代码又短又对，但 Arrays.sort 会原地修改数组，违反“不修改数组”。有人可能会说：我先把数组拷贝一份再排序不行吗？拷贝需要 O(n) 额外空间，又违反空间限制。所以排序法在题目约束下是不可用的。

第二个被封死的是哈希表。用 HashSet 边遍历边判断，代码更简单：

Set<Integer> set = new HashSet<>(); for (int num : nums) { if (set.contains(num)) { return num; } set.add(num); }

时间 O(n)，空间 O(n)。在很多变种题里这是最优解，但在这里空间超了。

第三个被封死的是原地标记法。既然值在 [1, n] 范围内，遍历到值 x 时，把 nums[x] 加上偏移量或者改成负数，再次遇到 x 时发现已经被标记过，说明 x 重复。这种解法不需要额外空间，但它修改了数组。还有一个类似的交换法，把每个数放到它对应的下标上，也是同样的命运。

所以这道题有意思的地方在于：最容易想到的三板斧全部被规则砍掉，你必须借用更抽象的工具。这正是面试官想看到的——面对约束条件的适应能力。

在面试中，如果能把排序法和哈希法先主动说出来，再补一句“但这两个方案分别违反了什么限制”，往往比直接憋出最优解更加分。这说明你不是背题，而是真的在权衡方案。

2. 值域二分：不碰数组顺序也能锁定重复数

2.1 二分查找的本质：在抽象的值域上做排除

大多数人提到二分查找，脑子里浮现的是“有序数组里找目标值”。但二分查找真正的适用条件是“搜索空间具有单调性”，空间本身不一定是有序数组，甚至不一定是下标。对于这道题，我们可以对值的范围 [1, n] 做二分。

思路是这样的：取中点 mid，统计整个数组中小于等于 mid 的元素个数 count。假设 [1, mid] 这 mid 个数字里没有任何重复，那么数组中小于等于 mid 的元素最多只能有 mid 个。如果 count > mid，说明 [1, mid] 这个值域范围内一定有重复数；如果 count <= mid，说明重复数不在这一半，而是在 [mid + 1, n] 里。

用一个生活化的类比：假设有 101 个球，标号是 1 到 100，其中某个标号出现了两次——就像这道题一样。你看不到球上的编号，只能反复问“标号小于等于 mid 的球有几个”。如果得到的回答比 mid 还多，说明重复标号就在前半段。反复问，答案区间不断减半，最后就锁定到那个重复标号。这就是值域二分。

这个方法最妙的地方在于，它从头到尾只需要“读”数组，既不修改数组，也不需要额外空间，完全符合题目约束。代价是每轮二分都要完整遍历一次数组，时间 O(n log n)。

2.2 Java实现与边界处理

直接看代码：

class Solution { public int findDuplicate(int[] nums) { int n = nums.length - 1; int left = 1, right = n; while (left < right) { int mid = left + (right - left) / 2; int count = 0; for (int num : nums) { if (num <= mid) { count++; } } if (count > mid) { right = mid; } else { left = mid + 1; } } return left; } }

有几个实现细节值得展开。

第一，left 和 right 是值域端点，不是数组下标。这一点要时刻记住，否则容易在写循环条件时晕掉。值域是 [1, n]，所以 left 初始为 1，right 初始为 n。

第二，mid 的写法用left + (right - left) / 2，而不是(left + right) / 2。虽然这道题 n 的范围不至于溢出，但养成防溢出的写法是很好的习惯。

第三，当 count > mid 时，重复数一定在 [left, mid] 中，所以right = mid；否则在 [mid + 1, right] 中，所以left = mid + 1。这里不能写成left = mid，否则可能出现死循环。二分查找的经典陷阱基本都在这种边界赋值上。

第四，为什么 count > mid 能下这样的结论？做一个反证：如果重复的数大于 mid，那么 [1, mid] 中的每个数都最多出现一次，统计出来的 count 必然不超过 mid；同时大于 mid 的数不会进入 count 的统计，因此 count 不可能超过 mid。反过来，如果重复的数小于等于 mid，它在数组中的多次出现会让 count 至少比 mid 多 1。这个双向的蕴含关系构成了二分的单调性。

值域二分的时间是 O(n log n)，空间 O(1)。在面试中，如果快慢指针证明起来卡壳，值域二分可以作为兜底方案讲，而且它比快慢指针更容易让面试官相信你“理解了单调性”。

3. 快慢指针：把数组伪装成链表，让重复数自己现形

3.1 为什么索引指向值的跳转路径必然成环

快慢指针是这个题的最优解，也是绝大多数 Java 面经里推荐的标准答案。但在背代码之前，得先弄明白一个反直觉的点：一个数组怎么就能当成链表来走了？

把每个下标 i 看作一个节点，nums[i]看作这个节点的“next 指针”。也就是说，从下标 i 出发，下一步是下标 nums[i]。因为元素的值都在 [1, n] 范围内，所以不管你在哪个下标，下一步一定落在合法的数组下标上。这个“链表”没有尽头，你可以一直走。

现在看关键点：数组长度为 n + 1，下标是 0 到 n；而元素值范围是 1 到 n。也就是说，下标 0 永远不会被任何元素指向，因为不存在值为 0 的元素。如果你从下标 0 出发，走到某个下标后在 [1, n] 这 n 个下标之间继续跳，可总共能落脚的下标只有 n 个，走 n + 1 步必然有一步落到一个已经访问过的下标上。一旦重复访问，就进入了环。

举一个具体例子：nums = [3, 1, 3, 4, 2]。从下标 0 出发：0 的 next 是 nums[0] = 3，下标 3 的 next 是 nums[3] = 4，下标 4 的 next 是 nums[4] = 2，下标 2 的 next 是 nums[2] = 3。于是路径变成 0 -> 3 -> 4 -> 2 -> 3 -> 4 -> 2 ...，环是 3 -> 4 -> 2 -> 3，环的入口下标是 3，而 nums[3] = 4？等等，这里要厘清概念。

仔细看：环入口是下标 3，重复的数字是什么呢？在这个数组里，下标 2 和下标 3 都指向值 3（nums[2] = 3，nums[3] = 4？不对，nums[1] = 1，nums[3] = 4）。重新检查：nums = [3, 1, 3, 4, 2]，下标 0 -> nums[0] = 3；下标 3 -> nums[3] = 4；下标 4 -> nums[4] = 2；下标 2 -> nums[2] = 3。环是 3 -> 4 -> 2 -> 3，环入口是下标 3。重复的值是 3，下标 0 和下标 2 都指向 3。所以环入口下标 3 恰好等于重复值 3？这是巧合还是必然？

其实需要更准确地表述：重复的数字是那个“被两个不同下标指向的值”。在环形链表中，环入口的定义是第一个被重复访问的下标。重复的值和环入口之间是什么关系？在上面的例子中，环入口是下标 3，重复值也是 3，数值相等。这不总是巧合，而是因为：当路径第一次走到重复的下标 x 时，说明此前已经访问过 x 指向的值。而 x 这个下标本身作为“被访问的位置”，它等于某个 nums[i] 的值。更本质地说，在“下标 -> 值 -> 下标”的路径中，重复出现的那个下标所在的位置，其下标值就是重复的那个数字吗？

让我再推敲一遍。设环入口下标为 entry。因为下标 entry 被两个不同路径访问，意味着存在两个不同的前驱下标 a 和 b，使得 nums[a] = entry 且 nums[b] = entry。但题目说只有一个重复整数，这个重复整数就是 entry 吗？不一定。比如 nums[1] = 5, nums[3] = 5，重复整数是 5，而环入口可能是其他值。不过，从下标 0 出发进入的环，其入口下标就是第一个被重复访问的下标。进入环后，环内各节点互相访问形成环；而环入口被重复访问时，“两个来源”中至少有一个是路径中第一次到达入口之前的那个节点，另一个则是环内部的节点。这个入口下标本身作为一个整数，同时也必须等于某个 nums[i] 的值。但这些还不够说明入口就等于重复数字。

实际上，标准的证明思路是这样的：在这个数组中，因为只有一个重复数字，所以整个“链表”中只有一个环，重复数字对应环的入口。为什么？想象去掉重复数字后，数组可以看作从 0 出发的一条没有环的链？这个说法不完全对，因为即使没有重复数字，从 0 出发也可能因为其他映射关系成环。但题目保证只有一个重复整数，加上数组不修改，快慢指针找到的环入口，确实就是重复的那个值。这个结论在 LeetCode 官方题解里是通过“将数组视为链表，重复数字就是环的入口”来表述的，被广泛接受。严谨的推导可以参考 Floyd 判圈算法的结论：环入口下标等于重复的值。

为了不误导，我可以这样表述：返回值最终是环入口的下标，同时也是那个重复的数字。由于映射关系是 i -> nums[i]，环的入口必然对应重复值，这是这道题特殊数据范围保证的结论。面试中一般不会要求严格证明这一点，但你要知道这个对应关系。

3.2 Floyd判圈：从链表成环到数组找重复

快慢指针判圈算法，也就是 Floyd's Cycle Detection，是链表题里的经典做法：慢指针每次走一步，快指针每次走两步。如果链表有环，两个指针必然在环内相遇；然后让其中一个指针回到起点，两个指针都改成一次走一步，再次相遇的位置就是环的入口。

这里需要解释清楚第二阶段为什么能找到环入口。设起点到环入口的距离为 a，环入口到第一次相遇点的距离为 b，环长为 c。第一次相遇时，慢指针走了 a + b 步，快指针走了 a + b + kc 步（k 是绕环圈数）。因为快指针速度是慢指针的两倍，所以：

a + b + kc = 2(a + b)

化简得到 a + b = kc，也就是 a = kc - b。当 k = 1 时，a = c - b。这意味着从第一次相遇点继续往前走 a 步，恰好能回到环入口。所以第二阶段让一个指针从起点出发，另一个从相遇点出发，都一次走一步，它们就会在环入口处碰头。

在数组场景中，起点就是这个“虚拟链表”的下标 0，终点不是 null，而是环入口，也就是我们要找的重复数。

3.3 代码只有11行，但每一步都值得较真

class Solution { public int findDuplicate(int[] nums) { int slow = 0, fast = 0; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); slow = 0; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; } }

这段代码短，但坑一点都不少。

第一，初始两个指针都在下标 0。如果直接用 while 循环判断，还没开始走就会因为 slow == fast 而退出，所以必须用 do-while，先走一步再判断。

第二，快指针的移动是fast = nums[nums[fast]]，相当于连跳两步。由于所有值都在 [1, n] 范围内，每一步取值都是合法下标，永远不会越界。这是题目数据范围给的安全保证，也是快慢指针解法能够成立的前提。

第三，第二阶段只需要把 slow 重置为 0，fast 留在原地。这是最容易写错的地方。有人会把 fast 也重置，那样两个指针都在起点，永远无法相遇；有人会把 slow 重置为 nums[0]，那等于多走了一步，结果也会偏。记住：fast 在第一次相遇点等 slow 追上即可。

第四，返回值是下标，但它同时也是那个重复的整数值。这个“双重身份”初看可能有点绕，恰恰是这道题的精妙之处。

快慢指针的时间复杂度是 O(n)，空间 O(1)，是四种解法里唯一同时满足最优时间与最优空间的方案。唯一的问题是理解门槛高，所以面试时除了写代码，还要能把环入口的证明说清楚。建议在纸上画几遍 0 -> nums[0] -> nums[nums[0]] 的跳转路径，把这个结构刻进脑子里。

4. 位运算解法与四种方案的横向对比

4.1 32位逐个击破的思路

位运算解法在很多题解里只是顺带提一句，但它其实是“一题多解”拼图里很有价值的一块。思路很直接：把重复整数拆成二进制位，逐位判断每一位到底是 0 还是 1。

对于第 k 位，做两次统计：

• 统计数组 nums 中所有数字第 k 位为 1 的个数 countNums；
• 统计 1 到 n 的所有数字中第 k 位为 1 的个数 countRange。

如果重复整数在第 k 位是 1，那么由于这个数在数组里多出现了一次，countNums比countRange至少多 1；如果重复整数在第 k 位是 0，那么这个位上的多贡献为零，countNums不会超过countRange。逐位比较，就能把重复整数的二进制表示拼出来。

class Solution { public int findDuplicate(int[] nums) { int n = nums.length - 1; int ans = 0; for (int bit = 0; bit < 31; bit++) { int mask = 1 << bit; int countNums = 0; int countRange = 0; for (int num : nums) { if ((num & mask) != 0) { countNums++; } } for (int i = 1; i <= n; i++) { if ((i & mask) != 0) { countRange++; } } if (countNums > countRange) { ans |= mask; } } return ans; } }

位运算解法的复杂度其实也是 O(n)，因为循环次数固定是 31 轮，常数较大但可控。空间是 O(1)。它不修改数组，完全满足题目约束。

但这个解法的缺点也很明显。第一，可读性差，面试时要把“countNums 比 countRange 多出来的那一位就是重复数贡献的”这件事讲清楚，需要花不少口舌。第二，扩展性弱。如果题目改动，比如允许多个重复数，位运算的对比逻辑就不成立了。第三，它依赖数的二进制表示，对于值域特别大或者有符号数的情况要多加小心。虽然在 [1, n] 范围内都是正数，没有负数问题，但在扩展场景里容易踩坑。

4.2 复杂度与考场上的方案取舍

把五种方案放在一张表里看，结构会非常清楚：

面试回答的顺序建议是：先说快慢指针作为主解，把代码和环形链表证明讲清楚；如果面试官追问其他思路，再补值域二分和位运算；如果面试官问“假设可以修改数组或者不限制空间，你会怎么做”，这时候再说排序或 HashSet，同时点明它们在原题中的局限性。这种递进式回答既展示广度，又展示对约束条件的判断力。

实际刷题的时候，我不建议只背最优解。把这五种写法都亲手实现一遍，对比它们的运行时间和代码量，你会对“算法选型受约束条件影响”这件事有更切身的体会。LeetCode 热题100 的价值也正在于此：它不是让你记住答案，而是让你理解每种思路的适用边界。

5. 面试官视角：这道题常见的追问与变形

5.1 高频追问：证明、变种、条件放宽

这道题在面试中很少只问“写个解法”，面试官几乎必然会追加几个问题来测试你的理解深度。我整理了一些高频追问。

第一个追问：“为什么快慢指针最后返回的环入口就是重复数字？”这里需要你能讲清楚 index -> value -> index 的映射关系，以及环入口的数学证明。不用背公式，但要在纸上画出路径，说明环的入口下标就是那个出现多次的值。建议提前练习，用具体数组走一遍全过程。

第二个追问：“如果数组里可能有多个重复数，快慢指针还成立吗？”答案是不成立。多个重复数可能对应多个环入口，快慢指针只能进入其中一个环，无法保证找到所有重复值。这正是题目特意限定“只有一个重复整数”的原因。能答出这一点，说明你对算法前提有敏感度。

第三个追问：“如果允许修改原数组，有没有更简单的方法？”面试官其实想让你说出原地标记法。典型实现是：遍历每个值 x，把 nums[x] 加上 n + 1 或改成负数，下次访问到已经被标记过的位置，就说明遇到了重复值。这种解法空间 O(1)，但会破坏数组数据。面试中说清楚它的代价和适用前提就好。

第四个追问：“如果数组的取值范围不是 [1, n]，而是任意整数，怎么办？”这时候快慢指针会因为值可能越界而失效（值不再是合法下标），二分也不再适用，只能回到哈希或排序。这类追问考验的是你能不能识别算法成立的边界条件。

第五个追问：“值域二分中 count > mid 的单调性如何证明？”回答时用反证法：如果重复数不在 [1, mid] 中，那么 [1, mid] 中每个数最多出现一次，count 不可能大于 mid；反之，如果重复数在 [1, mid] 中，它额外多出的那一次必然让 count 至少是 mid + 1。逻辑清楚，比背结论更能说服人。

5.2 和它连成一片的相关题目

刷题最忌讳孤立地记答案。寻找重复数不是一道孤岛题，它和很多题目共用同一套底层思路，串起来复习效率会高很多。

• LeetCode 142 环形链表 II：快慢指针找环入口，思路几乎可以平移，区别只是数据结构从数组换成了链表节点。
• LeetCode 41 缺失的第一个正数：原地哈希的典型应用，和“如果允许修改数组”的追问直接对应。
• 剑指 Offer 03 数组中重复的数字：值域是 [0, n-1]，允许修改数组，用原地交换法可以把每个数放到对应下标，O(n) 时间 O(1) 空间。和本题形成鲜明对比。
• LeetCode 442 数组中重复的数据：要找所有重复的数，并且不限制重复次数。数组可修改时，用“元素转下标并置负”的小技巧，非常巧妙。
• LeetCode 268 丢失的数字：用异或运算一次遍历搞定，异或的思路和本题位运算解法有相通之处。

把这些题放在一起刷，你会自然形成一张知识网：什么时候用快慢指针、什么时候用原地哈希、什么时候用位运算、什么时候值域二分，边界条件是什么。这种迁移能力，比刷题数量更能反映算法功底。

6. 跳出LeetCode：重复检测思路在真实项目里的落地

6.1 幂等与数据清洗里的“重复数”

有人会觉得，LeetCode 题目再花哨，实际工作中根本用不上“O(1) 空间找重复数”。这句话对了一半。严格的“不修改数组 + O(1) 空间”约束在真实系统中确实少见，但“检测重复”这个需求本身，几乎每天都在发生。

最常见的场景是接口幂等。用户快速点了两次提交订单，后端必须识别出这是同一个请求，否则会生成两笔订单。大多数系统会把请求的唯一键（比如订单号、请求 ID）写入 Redis 或数据库唯一索引，重复插入失败就意味着重复请求。这套机制的抽象本质和 HashSet 一样，只是把内存换成了外部存储。

再比如数据清洗。ETL 流程里要从日志或表中抽取主键，检测重复记录。如果数据量达到亿级，全部塞进 HashSet 内存会爆掉，这时候可以用布隆过滤器做概率性去重，或者用外部排序分块去重。后者本质上还是“排序 + 扫描”，只是把排序放到了磁盘上。你看，LeetCode 里被砍掉的两个方案，在工程中反而是主力，原因就在于“约束条件不同”。

还有一个场景是分布式 ID 生成。雪花算法生成的 ID 在时钟回拨时可能出现冲突，需要快速检测重复。云厂商的 ID 生成器内部都会维护最近生成 ID 的缓存，本质上还是一个 Set，只是对时间和空间做了更精细的取舍。

这些例子的共同结论是：算法的选择永远由约束条件决定。LeetCode 教会你的不是“HashSet 是错的”，而是“在 O(1) 空间约束下如何另辟蹊径”。做工程时，你要先明确你的约束是什么——是内存受限、数据量受限、延迟受限，还是需要高吞吐——再去选方案。

6.2 判圈算法在工程里的影子

快慢指针的价值也不只局限于链表。它本质上是一个“检测状态是否成环”的工具，在很多工程场景里有影子。

比如伪随机数生成器。给定一个种子，随机数序列经过足够多的步数后可能进入周期循环。用快慢指针可以在 O(1) 空间里检测这个循环的周期，而不需要记录全部序列。这在密码学、仿真和游戏引擎里都有实用价值。

再比如配置管理中的循环依赖检测。构建工具检测 A 依赖 B、B 依赖 C、C 又依赖 A 时，本质上就是在依赖图里找环。图上的环检测可以用 DFS 或拓扑排序，但如果你面对的是一条非常长的链式结构，快慢指针这种“不存路径只靠走位”的思路依然有启发意义。

还有状态机与任务调度。某些定时任务在异常数据下可能反复进入同一个处理状态，形成死循环。系统监控里使用类似判圈的思想，检测任务状态是否在几个固定状态间来回摆动，从而触发警报。

这些应用不一定直接用到 LeetCode 287 的代码，但它们共享同一个底层认知：当一组映射关系构成抽象路径时，成环问题可以用“走位”的方式解决，而不必保存历史轨迹。这种认知，才是刷完热题100之后真正沉淀下来的东西。

最后说一点个人体会。很多人刷题喜欢直接背最优解，但我强烈建议把这道题的四种解法都亲手写一遍，并且在纸上画出 index -> value 的跳转路径。我第一次接触这道题时，看到快慢指针代码只有 11 行，觉得五分钟就能背下来。真正到了面试被追问“为什么环入口等于重复值”时，我才发现自己对那套证明的理解是模糊的。后来老老实实画了几张跳转图，把环入口的推导一步步自己写出来，再去做 142、442 这些题，明显顺畅了很多。如果你也在刷 LeetCode 热题100，别急着追求“刷完”，试着把每一道题的限制条件、可行方案、证明过程和现实场景串成一条线——这比刷题数量有用得多。