Leetcode:Two sum (9ms)(hash table)(Analysis & solutions)

Two sum complete codes for testing.

Here provides the complete two sum codes. You can copy and past into VC++ for convenient testing/debugging/learning. 

Method 1:

1. using map (a hash method) to sort the numbers in ascending order (Think about what's the potential problem with map to sort the vector?) For detail description please refer to the link: CLICK HERE
Note: There are potential bugs inside and it's for you to debug out and make it perfect!

2. scan from two sides to effectively reduced the running time. 


Method 2:
When using hash table, the potential problem is that if there are same integers in the input vector, they will be overwrite. So, here we using the general SORT to sort the input vector. But the problem is that we need find out the index in the original input. 

Code with method 1:

///////////////////////////////////////////////////

//Two sum problem

///////////////////////////////////////////////////

# include "stdafx.h"

# include <cstdlib>

# include <iostream>     // std::cout

# include <algorithm>    // std::sort

# include <vector>       // std::vector

# include <map>          // std::map

using namespace std;

//using map

class Solution {

public:

       vector<int> twoSum(vector<int> &number, int target){

              map<int,int> mm;

              map<int, int>::iterator begin_it;//defind an iterator only

              map<int, int>::iterator end_it;//defind an iterator only

              vector<int> nn;

              for (int i = 0; i < number.size(); i ++){

                     mm[number[i]] = i;     //Note that the 'number', namely the first item in map is in ascending order.

              }

              begin_it = mm.begin(); //in the first real item

              end_it = mm.end();//in the last item (no number is referred here)

              --end_it;//in the last real item

              int sum = 0;

              for (int i = 1; i <= mm.size() - 1; i++){

                     sum = begin_it->first + end_it->first;

                     if (sum > target){

                           --end_it;

                     }

                     else if (sum < target){

                           ++begin_it;

                     }

                     else{

                           nn.push_back(begin_it->second +1);

                           nn.push_back(end_it-> second +1);

                           break;

                     }

              }

              return nn;

       };

};

int main(int argc, char *argv[])

{

       //problem 1, two sum

       vector<int> mm, nn;

       mm = { 2, 3, 1, 7, 6 };

       int target = 13;

       Solution s;

       nn = s.twoSum(mm, target);

       cout << "the solution is";

       cout << nn[0]; cout << nn[1];

       cout << "\n";

       cout << "HELLO:\n";

       cout << "\n";

       cout << "  Hello, world!\n";

       int age; //in order to keep the window

       cin >> age;

       return 0;

}







Code with method 2:

/////////////////////////
//  (12ms)

class Solution {

public:

       vector<int> twoSum(vector<int> &number, int target){

              vector<int> mm = number;

              //sort mm

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

              vector<int> nn;

              //two directional searching

              int j = 0;

              for (int i = 0; i <= mm.size() - 1;){

                     int sum = mm[i] + mm[mm.size() - 1 + j];

                     if (sum > target){

                           --j;

                     }

                     else if (sum < target){

                           ++i;

                     }

                     else{

                           //when searching finish, find out the original index in <number>

                           int flag1 = 0, flag2 = 0;

                           for (int m = 0; m<mm.size(); m++){

                                  if (number[m] == mm[i] && flag1 == 0){

                                         nn.push_back(m + 1);

                                         flag1 = 1;

                                  }

                                  else if (number[m] == mm[mm.size() - 1 + j] && flag2 == 0){

                                         nn.push_back(m + 1);

                                         flag2 = 1;

                                  }

                                  else if (flag1 == 1 && flag2 == 1){

                                         return nn;

                                  }

                           }

                           if (flag1 == 1 && flag2 == 1)return nn;//in case this is not implemented in the for loop

                     }

              }

              return nn;

       };

};

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
revised 9ms

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> numTmp=nums;
        
        //sort
        sort(numTmp.begin(), numTmp.end());
        
        vector<int> result;
        for (int i=0; i<numTmp.size(); i++){
            for (int j=numTmp.size()-1; j>i;j--){
                if(numTmp[i]+numTmp[j]==target){
                    //find out the original index
                    int idxOne=-1, idxTwo=-1;
                    for (int x=0;x<nums.size();x++){
                        if(nums[x]==numTmp[i] && idxOne==-1){
                            idxOne=x;
                        }
                        else if(nums[x]==numTmp[j] and idxTwo==-1){
                            idxTwo=x;
                        }
                    }

                    result.push_back(idxOne);
                    result.push_back(idxTwo);
                    return result;

                }
                else if(numTmp[i]+numTmp[j]<target) {
                    break;
                }

            }
        }
        return result;
    }

};





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
original code 172ms

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> numTmp=nums;
        vector<int> result;
        for (int i=0; i<numTmp.size(); i++){
            for (int j=i+1; j<numTmp.size();j++){
                if(numTmp[i]+numTmp[j]==target){
                    
                    result.push_back(i);
                    result.push_back(j);
                    return result;

                }

            }
        }
        return result;
        
        
        
    }
};