【Leetcode】442. 數組中重複的數據

題目鏈接：數組中重複的數據

題目描述：

給你一個長度為 n 的整數數組 nums ，其中 nums 的所有整數都在範圍 [1, n] 內，且每個整數出現 一次 或 兩次 。請你找出所有出現 兩次 的整數，並以數組形式返回。

你必須設計並實現一個時間複雜度為 O(n) 且僅使用常量額外空間的算法解决此問題。

分析：

1）題目要求的時間複雜度為O(n)，空間複雜度為O(1)。說明需要使用哈希錶，但不能借助另外的哈希錶。

2）又因為數組長度為n，索引是[0,n-1]，數據範圍是[1,n]，所以可以使用原地哈希的方式。即原地修改數組nums為哈希錶。

具體方法有：

方法一：將nums[i]%n作為新的索引j，j的範圍為[0,n-1]，若nums[j]<n，說明nums[i]%n是第一次出現，將nums[j]+=n。那麼之後若nums[j]>n，說明nums[i]%n是第二次出現。

方法二：將|nums[i]|-1作為新的索引j，（|nums[i]|錶示取絕對值），j的範圍為[0,n-1]，若nums[j]>0，說明|nums[i]|-1是第一次出現，將nums[j]取反。那麼之後若nums[j]<0，說明|nums[i]|-1就是第二次出現。

代碼如下：

var findDuplicates = function(nums) {
    const n=nums.length;
    let res=[]
    for(let i=0;i<n;i++){
        if(nums[nums[i]%n]>n)
            res.push(nums[i]%n==0?n:nums[i]%n);
        nums[nums[i]%n]+=n;
    }
    return res;
};

var findDuplicates = function(nums) {
    const n=nums.length;
    let res=[]
    for(let i=0;i<n;i++){
        let x=Math.abs(nums[i]);
        if(nums[x-1]<0)
            res.push(x);
        else
            nums[x-1]=-nums[x-1];
    }
    return res;
};