442. Find All Duplicates in an Array

題目連結：442. Find All Duplicates in an Array

題目描述

給定一個長度為 n 的整數陣列，其中陣列中的數字介於 1 到 n 之間（包括 1 和 n），有些元素可能會出現兩次，而其他元素只出現一次。請找出所有出現兩次的元素，並返回這些元素所組成的陣列。

限制條件

• 時間複雜度：要求為 O(n)
• 空間複雜度：要求為 O(1)，不能使用額外的空間（除了輸出陣列外）

解題思路

此題要求在不使用額外空間的情況下，找出所有重複出現的數字。我們可以利用原始陣列本身來記錄已出現的數字。由於陣列中的數字都在 1 到 n 之間，且都是正整數，我們可以通過將對應索引位置的數字取負，來標記該數字已經出現過。

具體步驟：

1. 遍歷陣列中的每一個數字 num。
2. 將 num 取絕對值後減一，得到索引 index = abs(num) - 1。
3. 檢查 nums[index] 是否為負數：
   • 如果是負數，表示該數字已經出現過一次，將 abs(num) 加入結果陣列。
   • 如果是正數，將 nums[index] 取負，標記為已出現。

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        const int n = nums.size();
        vector<int> ans;

        for (const int num : nums) {
            const int i = abs(num) - 1;
            nums[i] *= -1;
            if (nums[i] > 0) {
                ans.push_back(abs(num));
            }
        }
        return ans;
    }
};

時間與空間複雜度分析

• 時間複雜度：O(n)
  • 我們只需要遍歷一次陣列，對於每個元素執行常數時間的操作。
• 空間複雜度：O(1)（不計算輸出陣列）
  • 我們沒有使用額外的資料結構，直接在原始陣列上進行操作，符合空間複雜度的要求。