1. Two Sum

Mean:

给定一个数组nums和一个数target，求:id1和id2，id1和id2为数组nums两个不同的下标，使得nums[id1]+nums[id2]=target.

注意：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 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  using namespace std;typedef long long(LL);typedef unsigned long long(ULL);const double eps(1e-8);class Solution {public: vector
                  
                    twoSum(vector
                   
                    & nums, int target) { int cnt=0; vector
                    
                      ans; multimap
                     
                       mp; for(auto p:nums) mp.insert(make_pair(p,cnt++)); for(auto p:mp) { if(mp.count(target-p.first)>0) { multimap
                      
                       ::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
                       
                         ve; for(int i=0,tmp;i
                        
                         >tmp; ve.push_back(tmp); } int target; cin>>target; Solution a; vector
                         
                           ans=a.twoSum(ve,target); for(auto p : ans) cout<
                          <