leetcode 1----twoSum

題記：

       由于臨近畢業要找工作，雖然看了一遍資料結構和算法，但是總感覺心裡發虛。而且項目中所接觸到得程式設計都是基于其他方面得改進算法，總之本人程式設計能力有限，經常被人鄙視，是以下定決心，慢慢爬行，一點點刷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: [email protected] 
    > 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: [email protected] 
    > 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，大緻思想都是一樣得。