题记：

       由于临近毕业要找工作，虽然看了一遍数据结构和算法，但是总感觉心里发虚。而且项目中所接触到得编程都是基于其他方面得改进算法，总之本人编程能力有限，经常被人鄙视，所以下定决心，慢慢爬行，一点点刷leetcode，这也是写这些博客得缘由，记录在遇到题目时得分析思路，及解决方法。

                                                                                                                                                                                    ----------     我走的慢，但我从不后退。

======================================================================================================================================

题目1：

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

愚解：

   题目主要目的是，给定一个整数序列，同时给出一个目标整数，要求找出序列中两个数之后等于目标数得下标，并且小得下标在前面。

看到这个题目时，第一想法是一个两层循环，外层用来遍历序列，内从循环在遍历时判断外层对应得元素与内层对应得元素之后是否等于目标数，照这个想法实现了，但是提交后，提示 time limit exceed.代码如下：

/*************************************************************************
    > File Name: twoSum.cc
    > Author: Jerry Shi
    > Mail: jerryshi0110@gmail.com 
    > Created Time: 2014年12月27日 星期六 10时52分32秒
 ************************************************************************/

#include<iostream>
#include<vector>

using namespace std;

class Solution
{
	public:
		vector<int> twoSum(vector<int> &numbers,int target)
		{
			vector<int> result;

			int length = numbers.size()-1;
			int index1 = -1;
			int index2 = -1;
            
			int i,j;
			for(i=0; i <= length ; ++i)
	           {
			   for(j = i + 1; j <= length; ++j)
			   if( target == (numbers[i] + numbers[j]))
			   {
                              result.push_back(i+1);//index1
			      result.push_back(j+1);//index2
			   }
		   }
			
            
            if(!result.empty())
		return result;
	else
		cout << "No property index in given vector!" << endl;
		}
};

int main(void)
{
	vector<int> test;
    vector<int> result;

	test.push_back(2);
	test.push_back(7);
	test.push_back(11);
	test.push_back(15);

	int target = 9;
	Solution mtest;
	result = mtest.twoSum(test,target);
    
	int i;
	for(i = 0; i < result.size(); i+=2)
	{
		cout << "index1 = " << result.at(i) << "\t" << "index2 = " << result.at(i+1) << endl;
	}
	return 0;
}

 很明显这个题目得目的主要考察得是时间和空间效率方面，这种情况肯定不能使用两层循环因为复杂度达到N得平方了，所以要想怎么能够避免另一曾循环。再分析题目，由于时要求在序列中找到两个数得和等于目标数，肯定要用到一层循环，那么可以这样想，在每次循环访问序列元素时，我们用目标数减去访问得元素，然后查找该值是否存在于序列中，如果能够找到，那很明显该值和当前访问得元素就是我们要找得对象。这样以来，我们就要存储元素及其下标，而且要具有find功能，思考STL，我们可以用map<int，int> 符合我们得想法，key用来存储序列元素，value用来存储index，这样得话就把问题给解决了。详细代码如下：

/*************************************************************************
    > File Name: twoSum_hash.cc
    > Author: Jerry Shi
    > Mail: jerryshi0110@gmail.com 
    > Created Time: 2014年12月27日 星期六 14时52分27秒
 ************************************************************************/

#include<iostream>
#include<vector>
#include<iterator>
#include<map>
#include<set>

using namespace std;

class Solution
{
	public:
		vector<int> twoSum(vector<int> &numbers,int target)
		{
	 		map<int,int> map;
			vector<int> result;
           // map<int,int>::iterator it;
			int i  = 0;
			int other;
			for(i = 0; i < numbers.size(); ++i)
			{
				other = target - numbers.at(i);
				std::map<int,int>::iterator it = map.find(other);
				if(it != map.end())
				{
					result.push_back(it->second+1);//index2
					result.push_back(i+1); //index1
				}
				map.insert(pair<int,int>(numbers.at(i),i));
			}
            return result;
		}
};

int main(void)
{
	vector<int> test;
        vector<int> result;

	test.push_back(2);
	test.push_back(7);
	test.push_back(11);
	test.push_back(15);

	int target = 9;
	Solution mtest;
	result = mtest.twoSum(test,target);
    
	int i;
	for(i = 0; i < result.size(); i+=2)
	{
		cout << "index1 = " << result.at(i) << "\t" << "index2 = " << result.at(i+1) << endl;
	}
	return 0;
}

   然后提交，通过了测评，耗时 112ms，之后又看题目得solutions，说是用hash，还用得用得时boost中 unordermap，大致思想都是一样得。

leetcode 1----twoSum