题目的主要信息：

• 输入n个成对的数，前者是index，后者是value
• 对相同index的数对，value求和合并到一起
• 最后按照index的升序输出合并后的index和value

方法一：暴力解法

具体做法：

我们可以利用一个数组保存pair类型的变量，pair里面分别是index和value。每次新输入一对数，我们遍历数组查看是否已经有了这个index，如果有将新输入的value加到其后面就可以了，如果没有将index和value组成pair加到数组末尾即可。最后我们重载vector中的比较方式，让其对index排序，再输出即可。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool comp(pair<int, int>& a, pair<int, int>& b){ //重载比较，只与index比较
    return a.first < b.first;
}

int main(){
    int n;
    cin >> n;
    vector<pair<int, int> > num;
    for(int i = 0; i < n; i++){
        int index, value;
        cin >> index >> value;
        int j = 0;
        for(; j < num.size(); j++){ //遍历数组找到之前有无这个index
            if(num[j].first == index){ //有则累加
                num[j].second += value;
                break;
            }
        }
        if(j == num.size()) //没有则开辟一个新的index
            num.push_back(make_pair(index, value));
    }
    sort(num.begin(), num.end(), comp); //对index排序
    for(int i = 0; i < num.size(); i++)
        cout << num[i].first << " " << num[i].second << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(n^2\right)O(n^2)$O(n2)，两层遍历的复杂度是$O\left(n^2\right)O(n^2)$O(n2)，排序的$O\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n)相对较小，舍去
• 空间复杂度：$O\left(n\right)O(n)$O(n)，记录输入值的数组大小

方法二：哈希表

具体做法：

我们也可以用哈希表来识别不同的index，同时哈希表可以自动对插入的index进行排序。

根据输入，我们查看哈希表中是否有这个index，如果已经有了就直接将值加在其后面，如果没有则需要添加新的表项，整体类似方法一。

#include<iostream>
#include<map>
using namespace std;

int main(){
    int n;
    cin >> n;
    map<int, int> mp; //有序哈希
    for(int i = 0; i < n; i++){
        int index, value;
        cin >> index >> value;
        if(mp.find(index) != mp.end()) //不是新的index，就累加到之前的哈希表中
            mp[index] += value;
        else //否则添加新的index
            mp[index] = value; 
    }
    for(auto iter = mp.begin(); iter != mp.end(); iter++)
        cout << iter->first << " " << iter->second << endl;
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(nlo{g}_{2}n\right)O(nlog\_2n)$O(nlog2​n)，有序哈希表的查找与插入都是$O\left(lo{g}_{2}n\right)O(log\_2n)$O(log2​n)，一共$nn$n次循环
• 空间复杂度：$O\left(n\right)O(n)$O(n)，哈希表大小最大为所有元素都不同的时候，即$nn$n