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.

Q：给定一个整形数组nums，元素值位于[1,n]的范围内，且每个整数仅出现1次或2次，返回所有出现2次的整数。要求算法的时间复杂度是O(n)，空间复杂度是O(1)（仅使用常量个额外空间）。

Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n
  • Each element in nums appears once or twice.

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:** []

方法1：排序+遍历

不考虑复杂度要求，对原数组进行排序，通过比较相邻的元素是否相同得到所有出现2次的整数。
如使用归并排序（时间复杂度O(nlogn)，空间复杂度O(n)），总体的时间复杂度是O(nlogn)（O(nlogn)+O(n)=O(nlogn)），空间复杂度是O(n)。

  1. class Solution {
  2. public:
  3.     vector<int> findDuplicates(vector<int>& nums) {
  4.         vector<int> ret;
  5.         if(nums.size() <= 1){
  6.             return ret;
  7.         }
  9.         this->mergeSort(nums, 0, nums.size()-1);
  10.         for(int i=0; i<nums.size()-1; ){
  11.             if(nums[i] == nums[i+1]){
  12.                 ret.push_back(nums[i]);
  13.                 i += 2;
  14.             }
  15.             else{
  16.                 i += 1;
  17.             }
  18.         }
  19.         return ret;
  20.     }
  23.     void mergeSort(vector<int>& nums, int low, int high){
  24.         // （递归）归并排序
  25.         if(low < high){
  26.             int mid = (low + high)/2;
  27.             this->mergeSort(nums, low, mid);
  28.             this->mergeSort(nums, mid+1, high);
  29.             this->merge(nums, low, mid, high);
  30.         }
  31.     }
  33.     void merge(vector<int>& nums, int low, int mid, int high){
  34.         // 归并排序中的合并部分，合并两个有序的数组nums[low:mid],nums[mid+1,high]
  35.         vector<int> tmpNums(high-low+1, 0);
  36.         int i=low, j=mid+1, k=0;
  37.         while(i<=mid && j<=high){
  38.             if(nums[i] <= nums[j]){
  39.                 tmpNums[k++] = nums[i++];
  40.             }
  41.             else{
  42.                 tmpNums[k++] = nums[j++];
  43.             }
  44.         }
  45.         while(i<=mid){
  46.             // nums[mid+1,high]已经合并完毕，剩余nums[i:mid]部分未合并
  47.             tmpNums[k++] = nums[i++];
  48.         }
  49.         while(j<=high){
  50.             // nums[low:mid]合并完毕，剩余nums[j:high]部分未合并
  51.             tmpNums[k++] = nums[j++];
  52.         }
  54.         // 将合并后有序的数据拷贝到原数组中
  55.         for(i=0; i<tmpNums.size(); i++){
  56.             nums[low+i] = tmpNums[i];
  57.         }
  58.     }
  59. };

方法2：标记

若要时间复杂度在O(n)，则只能遍历一遍数组，关键在于遍历的同时修改数组，标记已经出现过一次元素。
注意数组中的元素的取值范围是[1,n]。
使用索引i遍历数组，定义k=|nums[i]|：

  • 如果nums[k-1]>0，标记nums[k-1] *= -1；

  • 如果nums[k-1]<0，证明k这个值已经出现过一次，加入到返回数组中即可。 ```cpp class Solution { public: vector findDuplicates(vector& nums) {

    1.   vector<int> ret;
    2.   if(nums.size() <= 1){
    3.       return ret;
    4.   }
    6.   int k=0;
    7.   for(int i=0; i<nums.size(); i++){
    8.       k = nums[i] > 0 ? nums[i] : -nums[i];
    9.       if(nums[k-1] > 0){
    10.           // k第一次出现
    11.           nums[k-1] = -nums[k-1];
    12.       }
    13.       else{
    14.           // k第二次出现
    15.           ret.push_back(k);
    16.       }
    17.   }
    18.   return ret;

    }

}; ```

运行效率评价：

Success
Details
Runtime: 52 ms, faster than 73.61% of C++ online submissions for Find All Duplicates in an Array.
Memory Usage: 33.6 MB, less than 42.55% of C++ online submissions for Find All Duplicates in an Array.