Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
给定整数数组，元素a[i]满足1 ≤ a[i] ≤ n，一些元素出现两次、其余的出现一次，请在线性时间和就地完成的情况下找出出现两次的元素。
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
思路：
参考 448. Find All Numbers Disappeared in an Array 找出数组中缺失的数 的做法，当置第i个数num[i-1]时，若元素已为负数，则说明之前出现过。
public class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> res=new ArrayList<>();
for(int i=0;i<nums.length;i++){
int val=Math.abs(nums[i])-1;
if(nums[val]<0) res.add(val+1);
nums[val]=-nums[val];
}
return res;
}
}
class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
res=[]
for i in range(len(nums)):
val = abs(nums[i])-1
if(nums[val]<0): res.extend([val+1])
nums[val]=-nums[val]
return res
