class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        int cur,tmp;
        for(int i=0;i<nums.size();i++) {
            if(nums[i]!=-1) {
                if(nums[i]==i+1) {
                    nums[i] = -1;
                    continue;
                }
                cur = nums[i] - 1;
                nums[i] = -2;
                while(nums[cur]!=-1 && nums[cur]!=-2) {
                    tmp = nums[cur] - 1;
                    nums[cur] = -1;
                    cur = tmp;
                }
                if(nums[cur] == -2) {
                    nums[cur] = -1;
                } else {
                    ans.push_back(cur+1);
                }
            }
        }
        return ans;
    }
};