查找数组中的所有重复项

给定一个整数数组，1 ≤ a[i] ≤ n（n = 数组的大小），一些元素出现两次，其他元素出现一次。

找到在此数组中出现两次的所有元素。

find-all-duplicates-in-an-array

样例

样例1

输入：
[4,3,2,7,8,2,3,1]
输出：
[2,3]

样例2

输入：
[10,2,5,10,9,1,1,4,3,7]
输出：
[1,10]

分析求数组中出现的重复数字
思路1、遍历数组，使用map 存储数组中的元素跟个数
            遍历 map val 大于1 的存到 集合就好

思路2、
 我们发现对数组的所有元素均有1 <= a[i] <=n ,也就是说对于所有a[a[i]-1]均为合法下标。由此引出如下做法：
        对于每个a[i]，我们将其对应的a[a[i]-1]取相反数，如果已经为负数则将a[i]加入答案中。

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: return a list of integers
     */
    public List<Integer> findDuplicates(int[] nums) {
        // write your code here
         if (nums == null || nums.length == 0) {
            return null;
        }
        Map<Integer,Integer> map = new HashMap<>();

        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer> list = new ArrayList<>();
        for (Integer key : map.keySet()) {
            if (map.get(key)>1) {
                list.add(key);
            }
        }
        return list;
    }
}

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: return a list of integers
     */
    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(nums[i]));
            } else {
                nums[index] = -nums[index];
            }
        }
        
        return res;
    }
}

源码地址: https://github.com/xingfu0809/Java-LintCode