1. 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;
}
* -----------------------------------------------------------------
* 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;
}
