数组中重复的数据

记牢这套「取绝对值 → 看 x-1 格子 → 负则重复、正则翻负打卡」，下面每一帧都在套它。

开局：数组全是正数，没有任何打卡。值域 1 到 8 正好对应下标 0 到 7，这是整套技巧成立的前提。

先看懂动作：读到值 4，就跑去下标 3（值 4 的「专属格子」），等下把那里翻成负号当打卡记号。每个值都去敲自己对应的那一格。

轮到第 0 位，值是 4，所以 x=4，跳去看它的专属格子 下标 3。

下标 3 还是正的，第一次来：把它翻成负号 -7（绿色）当打卡章。以后谁再来这格、看见负号就知道撞上重复了。

轮到第 1 位，值是 3，所以 x=3，跳去看它的专属格子 下标 2。

下标 2 还是正的，第一次来：把它翻成负号 -2（绿色）当打卡章。以后谁再来这格、看见负号就知道撞上重复了。

轮到第 2 位，值是 -2（先前被翻过负，取绝对值），所以 x=2，跳去看它的专属格子 下标 1。

下标 1 还是正的，第一次来：把它翻成负号 -3（绿色）当打卡章。以后谁再来这格、看见负号就知道撞上重复了。

轮到第 3 位，值是 -7（先前被翻过负，取绝对值），所以 x=7，跳去看它的专属格子 下标 6。

下标 6 还是正的，第一次来：把它翻成负号 -3（绿色）当打卡章。以后谁再来这格、看见负号就知道撞上重复了。

轮到第 4 位，值是 8，所以 x=8，跳去看它的专属格子 下标 7。

下标 7 还是正的，第一次来：把它翻成负号 -1（绿色）当打卡章。以后谁再来这格、看见负号就知道撞上重复了。

轮到第 5 位，值是 2，所以 x=2，跳去看它的专属格子 下标 1。

下标 1 的格子已经是负的（红色）——说明 2 早就打过卡了，这就是出现两次的数，收进答案：{ 2 }。

轮到第 6 位，值是 -3（先前被翻过负，取绝对值），所以 x=3，跳去看它的专属格子 下标 2。

下标 2 的格子已经是负的（红色）——说明 3 早就打过卡了，这就是出现两次的数，收进答案：{ 2, 3 }。

轮到第 7 位，值是 -1（先前被翻过负，取绝对值），所以 x=1，跳去看它的专属格子 下标 0。

下标 0 还是正的，第一次来：把它翻成负号 -4（绿色）当打卡章。以后谁再来这格、看见负号就知道撞上重复了。

八个位置全扫完。回头看，凡是负号的格子都被打过卡，整张数组本身就当了哈希表用，没多花一格额外空间。

揭晓：出现两次的是 2 和 3，答案 [2, 3]，和开头说的一致。整趟只走了一遍数组、没开额外数组，时间 O(n)、空间 O(1)。

边界：无重复返回空、单元素返回空；值域 1..n 是下标映射不越界的前提。

面试答法：值域 1..n 让值和下标一一对应，把出现与否编码进符号，数组自身兼作哈希表，故 O(1) 空间。