两数之和问题(运用map)

题目描述：

给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。

你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 1 到 n，不是以 0 开头。

解题思路：使用map键值对

C++中map提供的是一种键值对容器，里面的数据都是成对出现的,如下图：每一对中的第一个值称之为关键字(key)，每个关键字只能在map中出现一次；第二个称之为该关键字的对应值。

实现步骤：

1.数组的里面用键值对存起来，对应的值就是数组的下表

   map_sum[a[i]]=i;

2.寻找sum-a[i]在不在键值对里，且为了确保不是自己需要写下这条语句：map[sum-a[i]]!=map[a[i]],即

   if(map_sum.find(sum-a[i])!=map_sum.end()&&map_sum[sum-a[i]]!=i) 

样例：

给出 numbers = [2, 7, 11, 15], target = 9, 返回 [1, 2].

#include <iostream>

#include <map>
#include <vector>
using namespace std;
class Solution
{
public :
   bool Two_sum(vector<int> a,int sum)
   {
           int ret[2];
           bool flag=false;
       map<int,int> map_sum;
   for(int i=0;i<a.size();i++)
      map_sum[a[i]]=i;
           for(int i=0;i<a.size();i++)
           {
              if(map_sum.find(sum-a[i])!=map_sum.end()&&map_sum[sum-a[i]]!=i) 
                 {
                  flag=true;
ret[0]=i;
ret[1]=map_sum.find(sum-a[i])->second;
cout<<"["<<ret[0]<<","<<ret[1]<<"]"<<endl;
               }
           }
   return flag; 
       }
       
};


int main(void)
{
int a[8]={3,2,4,1,7,6,5,3};
int b=10;
    vector<int> arr(a,a+8);
Solution S;
if(S.Two_sum(arr,10))
  cout<<"is ok"<<endl;
else
  cout<<"is not ok"<<endl;
return 0;
}