645. Set Mismatch ----E

Q:

The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.

Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.

Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]

Note:

1. The given array size will in the range [2, 10000].
2. The given array's numbers won't have any order.

A:

不用XOR，还要分。  就用a-b                 a^2 - b^2 

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        long n = nums.size();
        long sum=0, sum2 = 0;
        for(auto k : nums){
            sum += k;
            sum2 += k*k;
        }
        long t1= (1+n)* n /2;
        long t2 = n*(n+1)*(2*n+1)/6;
        
        int subOf2 = sum - t1; // dup - miss = sum - t1
        // dup^2 - miss^2 = sum2 - t2
        int addOf2 = (sum2-t2) / (sum - t1);
        int dup = (subOf2 + addOf2) / 2;
        int miss = (addOf2 - subOf2) / 2;
        vector<int> res{dup, miss};
        return res;
    }
};

错误：

int 相乘的时候，中间结果依然会用int。因此为防溢出，直接用long

------------------------解法 2   自己以前的思路，看见一个就找到其对应的位置------------

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        int dup = 0;
        for(int i =0;i<n;i++){
            if(nums[i] != i+1){
                int nextIndex = nums[i] - 1;
                if(nums[i] == nums[nextIndex]){
                    dup = nums[i];
                    break;
                }
                nums[i] = nums[nextIndex];
                nums[nextIndex] = nextIndex + 1;
                --i;
            }            
        }
        int diff = accumulate(nums.begin(), nums.end(),0) - n*(n+1)/2;
        int miss = dup - diff;
        vector<int> res{dup,miss};
        return res;
    }
};

Errors:

忘了做 --i;