今天带来两道题的分享，一道是P3613 【深基15.例2】寄包柜，一道是Q1. 错误的集合。这两道题都不难，先来看第一题，这道题看一眼就能知道可以用二维数组来做，但建好二维数组之后却发现，需要建一个 10⁵∗10⁵ 的数组，如果就这么提交肯定会超出内存限制。我已经提交过一个MLE的代码了，如下：

#include <bits/stdc++.h>
using namespace std;
struct Box {
    vector<int> cell; 
    
    Box() : cell(100000, 0) {}  
};
int main (){
    int n,m,cz,i,j,k;
    cin>>n>>m;
    vector<Box> box(n);
    for(int i=0;i<m;i++){
        cin>>cz>>i>>j;
        if(cz == 1){
            cin>> k>>box[i].cell[j];    
        } else{
            cout<<box[i].cell[j]<<endl;
        }
    }
    return 0;
}

那么此时就能引出一个STL库中你可能没用过的数据结构map，map可以把数据和序号映射起来，这样只需要储存存放东西的寄包柜就行了，没存放的不用存储，大大节省了空间，这里也给出我的代码。

#include <bits/stdc++.h>
using namespace std;

struct Box {
    unordered_map<int, int> cell;
    void set(int j, int value) {
        // if (value == 0) {
        //     cell.erase(j);  // 清空格子就从map中删除
        // } else {
            cell[j] = value;  // 否则存入
        // }
    }
    int get(int j) {
        auto it = cell.find(j);
        return (it != cell.end()) ? it->second : 0;
    }
};

int main() {
    int n, m, cz, i, j, k;
    cin >> n >> m; 
    vector<Box> box(n + 1); 
    for(int t = 0; t < m; t++) {
        cin >> cz >> i >> j;
        if (cz == 1) {
            cin >> k;
            box[i].set(j, k);
        } else {  // cz == 2
            cout << box[i].get(j) << "\n";
        }
    }
    
    return 0;
}

另一道题也是数据结构相关的，这道题你看着会有什么想法，是不是会想着枚举一遍，看看什么数有两个，什么数没有，这当然是可以的，提供一份代码。

class Solution {
    //先记录次数，然后从1枚举每一个数得到正确的数
    public int[] findErrorNums(int[] nums) {
        int[] count = new int[10001];
        int[] res = new int[2];
        int errorNum = -1;
        for (int num : nums) {
            count[num]++; //记录出现次数
            if(count[num] == 2) errorNum = num; //记录下错误数
        }
        res[0] = errorNum;
        //由于数组要求出现的值是从1到n，所以从1开始找正确的值
        for(int i=1; i <= nums.length; i++){
            if(count[i] == 0){ //如果找到一个没有出现的值，那么就是正确的值
                res[1] = i;
                break;
            }
        }
        return res;
    }
}

那当然我这么说就是有另一种方法，这道题可以从总体上来思考，既然是从1到n的数，那么我们便可以求和，第一个和是从1加到n，第二个和是数组的每个元素相加，那么这两个和之间的差是什么，便是加上重复的数再减去删除的数。得到这个还是求不出来两个数具体是多少，但看到两个数相减，如果我们能算出两个数相加的和不就能求出来，这两个数分别是什么了吗。那么怎么能得到两个数的和呢?我们可以由这个联想到平方差公式，而平方我们可以通过从1的平方加到n的平方得到一个和，再从数组的每个元素的平方相加得到一个和，这两个和之间的差便是平方差。通过掌握的这两个式子便可以求出重复的数和删除的数了，代码如下：

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
       int n = nums.size();
       int sum1=0,sum2=0,a,b;
       long sum3=0,sum4=0;
       for(int i=0;i<n;i++){
            sum1+=i+1;
            sum2+=nums[i];
            sum3+=(i+1)*(i+1);
            sum4+=nums[i]*nums[i];
       }
        a=sum2-sum1;
        b=(sum4-sum3)/(sum2-sum1);
        return {(b+a)/2,(b-a)/2};
    }
};