class Solution {
  public:
      int singleNumber(vector<int>& nums) {
  
          // 时间复杂度为O（N），空间复杂度为O（1）常数量
          int result=0;//由于第一个就要参与计算，所以必须初始化
          for(auto num:nums)
              result=result^num;
          
          return result;
  
          //下面方法也可行，但是时间与空间复杂度均为O（N）不满足题目要求
          // unordered_map<int, int> group;
          
          // for(int i=0;i<nums.size();i++)
          // {
          //     group[nums[i]]++;
          // }
  
          // int result;
          // for(auto it=group.begin();it!=group.end();it++)
          // {
          //     if(it->second==1)
          //         result= it->first;
          // }
  
          // return result;
      }
  };

class Solution {
  public:
      int missingNumber(vector<int>& nums) {
  
         //用异或来求
          int result=0;
  
          // a与a异或为0
          //异或满足交换律和结合律
          // 那么把这个result与数组内的每个值进行疑惑，就可以得出缺少哪个
          for(int i=0;i<nums.size();i++)
          {
              //如果是一一对应的时候i^nums[i]=0，其余的只要存在都必然能交换找到匹配的
              result=result^(i^nums[i]);
          }
  
          // 实际上的元素的值应该是到nums.size()而不是nums.size()-1
          int new_value= nums.size();
          result=result^new_value;
  
          return result;
  
      }
  };

class Solution {
  public:
      int missingNumber(vector<int>& nums) {
  
          //等差数列求和公式
          int value=nums.size()*(nums.size()+1)/2;
  
          int sum=0;
          for(auto num:nums)
              sum+=num;
  
          return value-sum;//就能找出缺少的那个数
      }
  };