题意概述

• 从0~n中按序给定n个数
• 要求找出0~n中缺失的数

方法一：求和公式

思路与具体做法

• 等差公式求前n项和n*(n+1)/2
• 再累加整个数组的值
• 两个相减就是所缺失数字

class Solution {
public:
    int solve(vector<int>& a) {
    	int sum=0,n=a.size();
        for(int i=0;i<n;i++){
        	sum+=a[i];
		} 
		return n*(1+n)/2-sum;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n\right)O(n)$O(n)，遍历了一遍数组
• 空间复杂度：$O\left(1\right)O(1)$O(1)，仅定义了一个整形变量sum

方法二：位运算

思路与具体做法

• 遍历整个数组，将所有元素异或，因为出现两次的元素异或为0，最后就剩下了出现一次的元素
• $a\oplus a=0a\oplus a=0$a⊕a=0：相同的两个数异或为0
• $a\oplus 0=aa\oplus 0=a$a⊕0=a：任意数和0异或为其本身
• $a\oplus b\oplus c=a\oplus c\oplus ba\oplus b\oplus c=a\oplus c\oplus b$a⊕b⊕c=a⊕c⊕b：异或具有交换律

class Solution {
public:
    int solve(vector<int>& a) {
    	int sum=0,n=a.size();
        for(int i=0;i<n;i++){
        	sum^=a[i]^(i+1);
		} 
		return sum;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(n\right)O(n)$O(n)，遍历了一遍数组
• 空间复杂度：$O\left(1\right)O(1)$O(1)，仅定义了一个整形变量sum