問題：
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?
Example:Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
大意：
給出一個整型數(shù)組停巷， 1 ≤ a[i] ≤ n （n為數(shù)組的尺寸）键俱，一些元素出現(xiàn)了兩次缀踪，另一些只出現(xiàn)一次得院。
找到所有數(shù)組中出現(xiàn)了兩次的元素娃圆。
你能不能不使用額外的空間褪储，在O（n）時間內(nèi)完成疗韵？
例子：輸入：
[4,3,2,7,8,2,3,1]
輸出：
[2,3]
思路：
題目說明了數(shù)組中元素的范圍寝蹈，那么可以依此創(chuàng)建一個長度為n的新整型數(shù)組李命，其每個位置的值大小表示對應數(shù)字出現(xiàn)的次數(shù)，遍歷原數(shù)組箫老，遇到那個數(shù)字就將新數(shù)組對應值的位置的元素值加一封字，就記錄下每個數(shù)字出現(xiàn)的次數(shù)了，之后找出出現(xiàn)次數(shù)為2的添加到結果List中即可耍鬓。
這個做法使用了額外的O（n）的空間阔籽，并不符合要求。
代碼（Java）：
public class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> result = new ArrayList<Integer>();
int[] count = new int[nums.length+1];
for (int i = 0; i < nums.length; i++) {
count[nums[i]]++;
}
for (int i = 1; i < count.length; i++) {
if (count[i] == 2) result.add(i);
}
return result;
}
}
他山之石：
public class Solution {
// when find a number i, flip the number at position i-1 to negative.
// if the number at position i-1 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;
}
}
這個做法在注釋中也解釋了牲蜀，遍歷數(shù)組笆制，沒遇到一個元素，將其值對應的位置上的那個元素取負數(shù)涣达，當然因為元素的值是從1開始的项贺，所以變成位置的時候都要減一，每次換成位置時都要用絕對值來算峭判，因為出現(xiàn)了兩次的元素开缎，在之前就已經(jīng)被變成負數(shù)了，所以借此可以判斷林螃，如果該位置的元素是個負數(shù)钠糊，說明之前出現(xiàn)過一次卑笨，就記錄下來罗侯。
這個做法就沒有用額外的空間业稼，時間復雜度也是O（n）。
合集：https://github.com/Cloudox/LeetCode-Record
