题解

题目难度：中等难度

知识点：暴力求解、map、vector

暴力求解：

所谓暴力求解法，根据题意分析出的所有可能的情况来一一研究，得到最终结果。

无论是排列生成还是子集枚举，两种思路： 直接遍历和递归构造。

直接遍历

优点：思路和程序都很简单
缺点：在于无法简便地减少枚举量——必须生成所有可能的解，然后一一检查。

递归构造

生成和检查过程可以有机结合起来，从而减少不必要的枚举。

回溯法是一种系统的搜索问题的解的方法。

基本思想：

从一条路前行，能进则进，不能进则退回来，换一条路再试。回溯法是一种通用的解题方法。
应用回溯法的时候，首先明确定义问题的解空间。解空间至少应该包含问题的一个解。确定了解空间后，回溯法从开始结点出发，以深度优先的方法搜索整个解空间。对于回溯法一般可以采用递归方式来实现。

方法（一）

方法（一）：暴力求解
#include<iostream>
#include<vector>
#include<sstream>
using namespace std;
int sum=0;
int f1(vector<int> v,int m,int l){
//利用双层循环i，j。用i表示第一个数，j表示第二给数。
    for(int i = 0;i < l -1; i++){
        for(int j = i+1;j < l;j++){
            if(v[i]+v[j] == m){
                sum += i+j;
            }
        }
    }
    return sum;
}
int main(){
    vector<int> v;
    int n;
    char c;
    int l=0;
    string s;
    cin>>s;
    istringstream ss(s);
    while(ss>>n){
        v.push_back(n);
        l++;
        ss>>c;
    }
    int m=v[--l];
    cout<<f1(v,m,l);
    return 0;
}

方法（二）

使用map<int,vector<int>> m其中m->frist代表数字。vector<int>表示该数字的下标。</int></int>

思路：

1：将输入分离数字放入vector<int> b，标杆值放入v;</int>

2：将第一步得到的b和v作为实参传入gets()函数。

3：在gets()函数中，依次取出b[i],判断与之相加何为 标杆值v的temp，即temp=v-b[i];

4. 首先判断m中用temp作为键值的元素是否存在，如果已经存在,取出其对应所用下标位置vec[j]，将所有vec[j]以及i加在res上。

5.把该数b[i],加入到map中。

【注】一边判断一边放入map，不会导致两个数的下标和重复计算。

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int gets(vector<int> b,int v)
{
    int n=b.size();
    int res=0;
    map<int,vector<int>> m;
    for(int i=0;i<n;i++)
    {
        int tmp=v-b[i];
        vector<int> vec;
        if(m.find(tmp)!=m.end())
        {
            vec=m.find(tmp)->second;
            for(int j=0;j<vec.size();j++)
                res=res+vec[j]+i;
        }
        vec=m[b[i]];
        vec.push_back(i);
        m[b[i]]=vec;
    }
    return res;
}
int main()
{
    vector<int> a;
    int m,cnt=0;
    char c;
    while(cin>>m)
    {
        a.push_back(m);
        cin>>c;
    }
    int n=a.size();
    int val=a[n-1];
    a.erase(a.end()-1) ;
    int res=gets(a,val);
    cout<<res;
    return 0;
}