LeetCode(一)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=9Output: index1=1, index2=2
问题は难しくなくて、すべて书くことができて、肝心なのは効率を见て、私が最初に思いついたのは2つのforが循环してネストして、実现して、大神と比べてまるで弱くて爆発しました!オオカミは1つのとても长い配列(0 Xffff)を定义して、配列の指针を使って、数値を指针のシフトに変えて、例えば数値は35で、それでは配列の指针を35にシフトして、そして35に値を割り当てて、このような方式でhashMapのような机能を构筑して、効率は言うまでもありません(leedcode Runtime:8 ms)しかし、空間的には多くの空間を浪費する可能性がある.空間で時間を変えるやり方は価値があるかどうか、取るべきかどうか分からない.
エントリーレベル:

	vector twoSum1(vector& nums, int target) {//leedcode Runtime: 620 ms
		int temp = 0;
		vector result;
		for (int i = 0; i < nums.size(); i++){
			temp = target - nums[i];
			for (int j = i + 1; j < nums.size(); j++){
				if (temp == nums[j]){
					result.push_back(i + 1);
					result.push_back(j + 1);
				}
			}
		}
		return result;
	}

上級者:

	vector twoSum3(vector& nums, int target) {//leedcode Runtime: 24 ms
		map IntHash;
		int temp = 0;
		vector result;
		//for (int i = 0; i < nums.size(); i++)
		//{
		//	IntHash[nums[i]] = i;
		//}
		for (int i = 0; i < nums.size(); i++)
		{
			temp = target - nums[i];
			if (IntHash.find(temp) != IntHash.end()){
				result.push_back(IntHash[temp] + 1);
				result.push_back(i + 1);
				return result;
			}
			else
			{
				IntHash[nums[i]] = i;
			}
		}
		return result;
	}

大神級:

	vector twoSum4(vector& nums, int target) {//leedcode Runtime: 8 ms
		vector result;
		int valueIndices[0Xffff] = { 0 };
		//int valueIndicesN[0xffff] = {0};
		for (size_t i = 0; i != nums.size(); ++i)
		{
			int value = target - nums[i];
			if (valueIndices[value + 0Xffff / 2] != 0)
			{
				result[0] = valueIndices[value + 0Xffff / 2];
				result[1] = i + 1;
				break;
			}
			else
			{
				if (valueIndices[nums[i] + 0Xffff / 2] == 0)
				{
					valueIndices[nums[i] + 0Xffff / 2] = i + 1;
				}
			}

		}
		return result;
	}