【LeetCode】.1.Two Sum

1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

UPDATE (2016/2/13): The return format had been changed to zero-based indices. Please read the above updated description carefully.
Subscribe to see which companies asked this question
【分析】
解析:入力配列が必ずしも並べ替えられているとは限らないため,二重ループ解を用いると,時間的複雑度がO(nの二乗)であり,データ量位置の場合,この方式は望ましくない.時間的複雑さを低減するために,まず入力データをソートすることができ,sort()関数の時間的複雑さはO(nlog 2 n);次に,二重ポインタの両側を「クランプ」することで,迅速に解くことができる.元の配列に対応する要素の下付き文字を出力する必要があることを考慮すると,並べ替え後に下付き文字が変化するため,並べ替え前に各要素の値とその下付き文字を記録する必要があり,これは構造体によって容易に解決できる.
【主な知識点】
     1.sort()関数の使用は、ノード型データ(各ノードに複数のデータが含まれる)のソートにはbool型関数アシストが必要であることに注意し、本プログラムでは、ノードに格納されている元の入力データ(value)を位置下付き(position)ではなくソートする必要があるため、アシスト関数cmpが必要である.ノードデータが1つ(一般的な配列)しかない場合、cmpはデフォルトでデフォルトで昇順に配列できます.sort(Array.begin(),Array.end(),cmp),sort()関数の最初の2つのパラメータは,並べ替えられる配列の始末位置を表す.
     2.ダブルポインタ「クランプ」法の検索思想
【解法】

struct node
{
	int value;//      
	int position;//          
};
bool cmp(node a,node b)
{
	return a.value<b.value;// value ，    
}
class Solution6 {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
		vector<int> indices;
		vector<node> Array;//  vector        ,             （  ）
		for(int i=0;i<nums.size();i++)
		{
			node temp;
			temp.value=nums[i];
			temp.position=i;
			Array.push_back(temp);
		}
		sort(Array.begin(),Array.end(),cmp);//        （value）    

        unsigned int High,Low;//            （  ）     
		High=Array.size()-1;//High        
		Low=0;//        
		while(Low<High)//    “  ”   
		{
			while(Low<High&&(Array.at(Low).value+Array.at(High).value>target))
				High--;
			while(Low<High&&Array.at(Low).value+Array.at(High).value<target)
				Low++;
			if(Array.at(Low).value+Array.at(High).value==target)
			{
				//         ，       （position）   ，      indices  
				if(Array.at(Low).position>Array.at(High).position)
				{
					indices.push_back(Array.at(High).position);
				    indices.push_back(Array.at(Low).position);
				}
				else
				{
				    indices.push_back(Array.at(Low).position);
				    indices.push_back(Array.at(High).position);
				}
				return indices;//      （                ）
			}
		}
		return indices;	//    ，    
    }
};