442. 數組中重復的數據

給定一個整數數組 a，其中1 ≤ a[i] ≤ n （n為數組長度）, 其中有些元素出現兩次而其他元素出現一次。

找到所有出現兩次的元素。

你可以不用到任何額外空間并在O(n)時間復雜度內解決這個問題嗎？

示例：輸入:
[4,3,2,7,8,2,3,1]輸出:
[2,3]

解題思路

將nums[i]中的元素放入其對應的下標中，因為1 ≤ a[i] ≤ n，在沒有出現重復的元素的情況下，應該是每一個元素都可以放在其對應的下標中，一旦出現重復的元素，就說明了會出現兩個元素放入一個下標的情況

代碼

class Solution {void swap(int[]nums,int l,int r){int t=nums[r];nums[r]=nums[l];nums[l]=t;}public List<Integer> findDuplicates(int[] nums) {List<Integer> res=new ArrayList<>();for(int i=0;i<nums.length;i++){while(nums[i]>=0&&nums[i]!=i+1){if(nums[nums[i]-1]==nums[i]){res.add(nums[i]);nums[i]=-1;break;} swap(nums,i,nums[i]-1);}}return res;}
}