1~N范围数组查找唯一重复元素时nums[abs(nums[i])-1]减1的原因

减1操作的核心原因 #

这个操作的本质是将1基的元素值映射到C++数组的0基下标，背后的逻辑基于两个给定前提：

• C++ 数组的下标从0开始计数，合法下标范围为 0 ~ 数组长度-1
• 题目明确数组所有元素的取值范围是1~N，不存在值为0的元素

如果不对元素值做减1处理，元素值1会对应到下标1，会永久浪费下标0的存储空间；同时这个写法是通用的映射方案，即使在数组长度为N的场景下（元素1~N），减1后也不会出现下标越界问题。本题数组长度为N+1，直接用元素值当下标也不会越界，但不符合常规的数值和下标一一对应的映射逻辑。

手动模拟出错的常见原因 #

你模拟得到错误结果大概率是忽略了以下两个代码细节：

• 每次计算下标前，必须先对nums[i]取绝对值：因为前面的遍历可能已经将nums[i]所在位置的元素标记为负数，只有取绝对值才能拿到原始的元素值
• 修改的是abs(nums[i])-1下标位置的元素值，不是当前i下标位置的元素值

模拟示例（供参考） #

举个简单例子验证：N=3，数组为[1,3,2,2]（长度4，重复值为2）

1. i=0，nums[i]=1，计算下标为abs(1)-1=0，nums[0]为1≥0，修改为-1，数组变为[-1,3,2,2]
2. i=1，nums[i]=3，计算下标为abs(3)-1=2，nums[2]为2≥0，修改为-2，数组变为[-1,3,-2,2]
3. i=2，nums[i]=-2，取绝对值为2，计算下标为2-1=1，nums[1]为3≥0，修改为-3，数组变为[-1,-3,-2,2]
4. i=3，nums[i]=2，计算下标为2-1=1，nums[1]为-3<0，返回abs(nums[i])=2，结果正确

相关代码 #

你提供的C++代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[abs(nums[i]) - 1 ] >= 0)
                nums[abs(nums[i]) - 1 ] = -nums[abs(nums[i]) - 1 ];
            else
                return abs(nums[i]);
        }
        return 0;
    }
};

内容的提问来源于stack exchange，提问作者Joshua