范围为-n到n的数组求首个重复值的O(1)空间通用解法问询

存在兼容负值范围的通用O(1)空间解法，前提是允许原地修改输入数组，且所有元素的绝对值不超过数组长度L（即-L ≤ 元素值 ≤ L），否则无法利用数组下标做原地标记。

实现思路 #

原有1~n范围的解法核心是用数组位置的符号标记访问状态，遇到原生负值时只需要先做值域偏移消除原生负号，再沿用相同的标记逻辑即可。

具体步骤 #

1. 值域偏移：设数组长度为L，第一次遍历数组，将所有元素加上L + 1，原本[-L, L]的取值范围会被偏移到[1, 2L + 1]，所有元素变为正数，后续负号就可以专门用来做访问标记。
2. 遍历标记：第二次遍历数组，对每个位置的元素执行以下操作：
   • 取当前元素的绝对值，减去偏移量L + 1还原得到原始值x = abs(a[i]) - (L + 1)
   • 取x的绝对值作为标记下标idx = abs(x)
   • 检查a[idx]的符号：
     • 如果已经为负，说明x之前已经出现过，直接返回x即为首个重复值
     • 如果为正，将a[idx]取反，标记为已访问
3. 遍历结束未找到则说明无重复元素，返回约定的异常值即可。

示例验证 #

以长度L=3的数组[-1, 2, -1]为例：

• 偏移后数组变为[3, 6, 3]
• 遍历到第一个元素，还原得x=-1，对应下标1，将a[1]改为-6
• 遍历到第二个元素，还原得x=2，对应下标2，将a[2]改为-3
• 遍历到第三个元素，还原得x=-1，对应下标1的元素已经为负，直接返回-1，符合预期。

复杂度说明 #

• 时间复杂度O(L)：仅两次线性遍历，所有操作都是常数时间
• 空间复杂度O(1)：仅使用临时变量，无额外存储空间开销

如果不允许修改原数组，目前没有通用的O(1)空间线性时间解法，若允许牺牲时间可以用原地排序后遍历的方案，但排序会打乱元素原有顺序，无法定位「第一个出现」的重复值，这种场景下只能使用哈希表的O(L)空间方案。

内容的提问来源于stack exchange，提问作者Zabir Al Nazi Nabil