C++中map的使用——用map解决“输出数组中和为定值的所有两（三）个数的组合”

末蓝、 2022-05-15 00:28 234阅读 0赞

思路：将数组中的数，按照数值—频率的形式储存到一个字典（map）中，然后对任意的键key，寻找另一个键key1 = sum - key，分三种情况，key1==key，key1!=key，key1不存在。注意每次计算完一对数，则将其从字典中删除。三的数相加的情况是两个数相加的 拓展，遍历所有键，对除去当前键的字典进行上述（两个数和）的算法。

# include<iostream>
    # include<vector>
    # include<map>
    
    using namespace std;
    
    void search_for_combination_sum(vector<int>* a, int sum){
        map<int,int> b;
        //数组的元素作为键，将频率作为值，初始化一个字典（map）
        for(auto i = a->begin();i!=a->end();i++){
            if(b.find(*i)==b.end()){
                b.insert(pair<int,int>(*i,1));
            }
            else{
                b[*i]++;
            }
        }
        //判断条件，b为空，即匹配成功一次
        while(b.size()>0){
            auto i = b.begin();
            auto iter = b.find(sum - (i->first));
            //三种情况
            //1,差值也是自己，直接删除
            if(iter == i){
                for(int k = 0;k<((iter->second)/2);k++){
                    cout << i->first << "->" << i->first << endl;
                }
                b.erase(i);
            }
            //2，差值存在
            else if(iter != b.end()){
                int num = min(i->second,iter->second);
                for(int k=0;k<num;k++){
                    cout << i->first << "->" << iter->first << endl;
                }
                b.erase(i);
                b.erase(iter);
            }
            //3.差值不存在
            else{
                b.erase(i);
            }
        }
    }
    
    void search_for_combination_sum_3(vector<int>* a,int sum){
        map<int,int> b;
        //和两个数的一样，字典储存频率
        for(auto i = a->begin();i!=a->end();i++){
            if(b.find(*i)==b.end()){
                b.insert(pair<int,int>(*i,1));
            }
            else{
                b[*i]++;
            }
        }
        while(b.size()>0){
            auto i = b.begin();
            int c = 0;
            int temp = 0;
            //遍历每一个元素
            temp = i->first;
            //只有一个，删除
            if(i->second == 1){
                b.erase(i);
                c = 1;
            }
            //不止一个，降低频率
            else{
                (i->second)--;
            }
            int sum_a = sum - temp;
            //拷贝剩下的内容
            map<int,int> b_c(b.begin(),b.end());
            //在剩下的频率内容中计算两个数的和
            while(b_c.size()>0){
                auto j = b_c.begin();
                auto iter1 = b_c.find(sum_a-(j->first));
                if(iter1==j){
                    for(int k = 0;k<j->second/2;k++){
                        cout << temp << "->" << j->first << "->" << j->first << endl;
                    }
                    b_c.erase(j);
                }
                else if(iter1!=b_c.end()){
                    int num = min(j->second,iter1->second);
                    for(int k =0;k<num;k++){
                        cout << temp << "->" << j->first << "->" << iter1->first << endl;
                    }
                    b_c.erase(j);
                    b_c.erase(iter1);
                }
                else{
                    b_c.erase(j);
                }
            }
            //之前没有删除的，现在删除
            if(c==0){
                b.erase(i);
            }
    
        }
    }
    
    int main(){
        vector<int>* a = new vector<int>;
        *a = {1,2,3,4,2};
        search_for_combination_sum(a,4);
        search_for_combination_sum_3(a,5);
        return 0;
    }