题目链接

力扣 645.错误的集合

不想戳的看下图

解题思路

循环嵌套

对于这道题，有很多种方法。首先想到的，应是循环嵌套。直接for循环两边寻找相同，并求得丢失的整数。代码就不展示了，想必大家都会写。
但时间复杂度O（n²），是相当高的，对于这题的数据范围，不适合用这个方法。

map

我们想到，可以使用STL里面的map。
代码如下：

class Solution {
    public int[] findErrorNums(int[] nums) {
    	int result[] = new int[2];
		Map<Integer, Integer> numMap = new HashMap<>();
		int len = nums.length;
		for (int i = 0; i < len; i++) {
            if (numMap.get(nums[i]) == null) {
                numMap.put(nums[i], 1);
            } else {
                numMap.put(nums[i], numMap.get(nums[i]) + 1);
            }
        }
		for (int key : numMap.keySet()) {
            int value = numMap.get(key);
            if (value == 2) {
                result[0] = key;
                break;
            }
        }
		for(int j =1;j<=len;j++){
            if(numMap.get(j)==null){
                result[1]=j;
            }
        }
		return result;
    }
}

哈希表

map是普通的计数法。我们在这里还有一种推荐：哈希表。
首次遍历求出出错集合的和，二次遍历建立哈希表，找到重复的元素，之后两和相减求出加上出错元素的值

代码如下：

class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] result = new int[2];
        int n=nums.length;
        int sum=n*(n+1)/2;
        int sum2=0;
        int x=-1;
        int[] temp = new int[nums.length+1];
        for(int i=0;i<nums.length;i++)
            sum2+=nums[i];
        for(int i=0;i<nums.length;i++)
        {
            if(temp[nums[i]]==0)
                temp[nums[i]]=1;
            else
            {
                x=nums[i];
                break;
            }
        }
        int cha=sum-sum2;
        result[0]=x;
        result[1]=x+cha;
        return result;
    }
}