Fast Find Duplicates

Solution.cpp

#pragma GCC optimize("Ofast")
static auto _ = [] () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return 0;
}();

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ret{};
        size_t i = 0;
        while (i < nums.size()) {
            if (nums[i] == i + 1) {
                ++i;
            } else if (nums[i] == nums[nums[i] - 1]) {
                ret.push_back(nums[i]);
                ++i;
            } else {
                if (nums[i] <= i) {
                    swap(nums[i], nums[nums[i] - 1]);
                    ++i;
                } else {
                    swap(nums[i], nums[nums[i] - 1]);
                }
            }
        }
        return ret;
    }
};