面试里遇到“数组元素都在 0 到 n-1 范围内，怎么找重复数字”时，原地置换是很经典的一种解法。它看起来像双层循环，但只要理解元素归位的过程，就会发现整体时间复杂度依然可以做到 O(n)。
先理解这类题为什么适合原地处理
题目给出的范围约束很关键。因为每个数字理论上都应该出现在与自己数值相同的下标位置，所以我们可以不断把当前元素交换到“它该去的位置”，相当于边遍历边整理数组。
为什么看起来像双层循环却不是 O(n²)
关键在于每次交换都在推进一个元素归位。某个数字一旦被放回正确位置，后面通常不会被无意义地反复搬动，所以总交换次数是受数组长度约束的，不会无限膨胀成平方级。
重复数字是怎么被发现的
当你准备把数字放到目标下标时，如果发现目标位置已经放着同样的值，就说明这个数字重复出现了。也就是说，重复不是靠额外集合统计出来的，而是在归位冲突时自然暴露出来。
它适合什么场景，不适合什么场景
这种方法节省额外空间，但前提是允许修改原数组，而且数字范围必须满足题目约束。只要这两个条件不成立，就该考虑 HashSet 或排序等别的思路。
结论
原地置换能做到 O(n)，不是因为循环层数少，而是因为每次交换都在推动元素归位。理解这一点，复杂度分析就不会被表面结构误导。
正文完
