空间复杂度O(1)

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size() - 1, res = 0, t;
        for(int i = 0; i < nums.size(); i ++){
            t = (nums[i] > n) ? (nums[i] - n) : nums[i];
            if(nums[t - 1] > n) {
                res = t;
                break;
            }
            nums[t - 1] += n;
        }
        for(int i = 0; i < nums.size(); i ++){
            while(nums[i] > n) nums[i] -= n;
        }
        return res;
    }
};