public class Solution {
// when find a number i, flip the number at position i1 to negative.
// if the number at position i1 is already negative, i is the number that occurs twice.
public List<Integer> findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
int index = Math.abs(nums[i])1;
if (nums[index] < 0)
res.add(Math.abs(index+1));
nums[index] = nums[index];
}
return res;
}
}
Java Simple Solution


Thank you!
I was thinking we need a way to "hash" the same number together without using extra space. I am inspired by the range of the input value (1  N), which seems fit the index of the input array (0  N1).
If I hash
num[i]
to indexnum[i]1
, then I need to store it at indexnum[i]1
smartly. I shouldn't make irrecoverable change to the element at that position, because I may need the element in the future. Again using the given range of input is (1  N), if flip it to the opposite I can still recover it usingMath.abs


Just wondering how this works.
For e.g. you are picking a value from array and you go to the point in array till this value to mark is negative.For e.g., if you have array [2, 5, 88, 123, 3455]; then how come nums[index] will not give ArrayOutBound exception ???
int index = Math.abs(nums[i])1;
if (nums[index] < 0)

@TechPrep Don't forget there is a assumption: "1 ≤ a[i] ≤ n (n = size of array)", there will not give ArrayOutBound exception

@TechPrep please read the restrictions, ok? Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.



I was just wondering if we have something like {{4,3,2,2,2,2,3,1}}. In that case, this returns the answer to be [2,2,3]. But from my understanding, the output should be [3] only as it is the only element that appears twice. Or is it okay to assume this is correct because the question does not specify exactly twice.

