題目網址：https://leetcode.cn/problems/find-all-duplicates-in-an-array/

題意：給一有 n 個數的 array nums, 每個元素值皆在 [1, n], 且每個元素可能出現 一次 or 兩次, 求所有出現兩次的數。

注意：使用 $O(n)$ time 和 $O(1)$ space 的演算法

Solution：

想法：將數字乘以負號來標記我們看到的數字的 index, 然後遍歷 nums 元素, 若 nums[i] > 0, 代表數字 i + 1 出現過兩次(類似 448. Find All Numbers Disappeared in an Array)

e.g. [1, 1, 2] ➔ [1, -1, 2], nums[i - 1] 決定數字 i 出現的次數

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;

        for (const auto& num : nums) {
            nums[abs(num) - 1] *= -1;

            if (nums[abs(num) - 1] > 0) {
                res.emplace_back(abs(num));
            }
        }

        return res;
    }
};
  • time：$O(n)$ ➔ 遍歷 nums
  • space：$O(1)$ ➔ 扣除返回的 array, 只需常數空間