LeetCode - 1. Two Sum1. Two Sum Problem's Link

 ----------------------------------------------------------------------------

Mean: 

給定一個數組nums和一個數target，求:id1和id2. (nums[id1]+nums[id2]=target,id1和id2為數組nums兩個不同的下标).

注意：nums中元素可重.

analyse:

如果nums中沒有重複元素，那麼可以用map做.

由于有重複元素，需要用multimap.

注意：使用map時，需要用count(key)來檢測是否存在key值，否則會出現錯誤.

Time complexity: O(N*logN)

view code

/**

* -----------------------------------------------------------------

* Copyright (c) 2016 crazyacking.All rights reserved.

*       Author: crazyacking

*       Date  : 2015-01-29-14.24

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long(LL);

typedef unsigned long long(ULL);

const double eps(1e-8);

class Solution {

public:

   vector<int> twoSum(vector<int>& nums, int target)

   {

           int cnt=0;

           vector<int> ans;

           multimap<int,int> mp;

           for(auto p:nums)

                 mp.insert(make_pair(p,cnt++));

           for(auto p:mp)

           {

                 if(mp.count(target-p.first)>0)

                 {

                       multimap<int,int>::iterator it1,it2;

                       if((p.first==target-p.first)&&(mp.count(p.first)==2))

                       {

                             it1=mp.find(p.first);

                             ans.push_back((*it1).second+1);

                             mp.erase(it1);

                             it2=mp.find(p.first);

                             ans.push_back((*it2).second+1);

                             break;

                       }

                       it1=mp.find(p.first);

                       it2=mp.find(target-p.first);

                       ans.push_back((*it1).second+1);

                       ans.push_back((*it2).second+1);

                       break;

                 }

           }

           sort(ans.begin(),ans.end());

           return ans;

   }

};

int main()

{

     int n;

     while(cin>>n)

     {

           vector<int> ve;

           for(int i=0,tmp;i<n;++i)

                 cin>>tmp;

                 ve.push_back(tmp);

           int target;

           cin>>target;

           Solution a;

           vector<int> ans=a.twoSum(ve,target);

           for(auto p : ans)

                 cout<<p<<endl;

     }

     return 0;

}