Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution:

1. Brute-force is O(N^N),

2. use Hash. in C++, it is unordered_map, not map. 

find in map has complexity of O(logN), find in unordered_map has complexity of O(1) average, O(N) worst case 
Space complexity is O(N)

3. Two pointers. Sort the vector, One pointer for a fixed value, the other one for searching, complexity O(NlogN): N for the fixed value, logN for searching

01

//2 sum

02	int i = starting; //头指针

03	int j = num.size() - 1; //尾指针

04	while(i < j) {

05	int sum = num[i] + num[j];

06	if(sum == target) {

07	store num[i] and num[j] somewhere;

08	if(we need only one such pair of numbers)

09

break;

10

otherwise

11	do ++i, --j;

12

}

13	else if(sum < target)

14

++i;

15

else

16

--j;

17

}

Complexity is O(NlogN)

K-sum complexity boundary is O(N^(K-1)).

Reference:

http://tech-wonderland.net/blog/summary-of-ksum-problems.html

In all two methods, either use hash or use two pointers or 3 pointers method.

Here we use hash: Two things need to pay attention.

1. index is starting from 1 not from 0

2. Hash find can not find it self

Code:

vector twoSum(vector &numbers, int target) {

   // first is the value, second is the index

   unordered_map group;

   for(int i=0; i

   {

       pair tmp(numbers[i],i);

       group.insert(tmp);

   }

   int id1, id2;

   unordered_map::iterator it;

   for(int i=0; i

   {

       id1 = i;

       unordered_map::iterator it = group.find( target - numbers[i] );

       if (it!=group.end()&& it->second!=i)

                {

         id2 = it->second;

         break;

       }

   }

    vector res;

   if (id1>id2)

   res = {id2+,id1+1};

   else

   res = {id1+1,id2+1};

   return res;

}