###### tags: `Leetcode` `medium` `array` `hash` `python` `c++`

# 442. Find All Duplicates in an Array

## [題目連結:] https://leetcode.com/problems/find-all-duplicates-in-an-array/description/

## 題目:
Given an integer array ```nums``` of length n where all the integers of ```nums``` are in the range ```[1, n]``` and each integer appears **once** or **twice**, return an array of all the integers that appears **twice**.

You must write an algorithm that runs in ```O(n)``` time and uses only constant extra space.

**Example 1:**

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

**Example 2:**

Input: nums = [1,1,2]
Output: [1]

**Example 3:**

Input: nums = [1]
Output: []

## 解題想法:
* 長度為n的數組，數值範圍為[1~n]，其中洽有兩數出現兩次，其餘皆只出現一次，求該兩數
* O(n) time
* O(1) space

* **技巧**:
* for i in nums:
* 將nums[i]值(pos)視為對應的位置，將該位置二次對應於nums中，即nums[pos]，將其取**負號**作為標記
* 原理:
* 一對一概念，當有值重複對應到相同的位置，則代表重複

## Python:

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        #要求O(1) space: 
        #for i in nums: 將num[i]值對應pos將其取負做為標記
        #一對一概念 當有人重複對應到相同pos 則代表重複
        res=[]
        for i in range(len(nums)):
            check_pos=abs(nums[i])-1 #因為範圍為1~n ，取位置需-1下標才為0
            if nums[check_pos]<0: #為負!! 代表一對多 重複
                res.append(abs(nums[i]))
            else:
                nums[check_pos]*=-1
        return res
result=Solution()
nums = [4,3,2,7,8,2,3,1]
ans=result.findDuplicates(nums)
print(ans)

## C++:

#include<bits/stdc++.h>
using namespace std;

class Solution{
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        int n=nums.size();
        for (int pos=0; pos<n; pos++){
            int check_pos=abs(nums[pos])-1;
            if (nums[check_pos]<0)
                res.push_back(abs(nums[pos]));
            else
                nums[check_pos]*=-1;
        }
        return res;
    }
};

int main(){
    vector<int> nums={4,3,2,7,8,2,3,1};
    vector<int> ans;
    Solution *res= new Solution();
    ans=res->findDuplicates(nums);
    for (auto val: ans){
        cout<<val<<" ";
    }
    return 0;
}