LeetCode [Easy] 1.Two Sum (by C/C++)

題目：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, and you may not use the same element twice.

範例：

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

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

解法：

1. 直觀解法：兩層迴圈比對所有組合，時間複雜度O(n^n)。 

	int* twoSum(int nums[], int numberSize, int target)
	{
	//排除數列個數小於2的情形，避免無法相加
	if( numberSize < 2 ) return NULL;
	else
	{
	int i , j ;
	int* ans = (int*)malloc(sizeof(int)*2);
	//注意迴圈數，避開自己
	for( i = 0; i < numberSize - 1; i ++ )
	{
	for( j = i + 1; j < numberSize; j ++ )
	{
	if( nums[i] + nums[j] == target )
	{
	ans[0] = i;
	ans[1] = j;
	return ans;
	}
	}
	}
	}
	return NULL;
	}

view raw TwoSum solution1 hosted with ❤ by GitHub
2. 簡易的Hash：取一段len長度的hash表，通過hash function : target-nums[i]-min尋找解，時間複雜度降低到O(n)。注意：若有極端資料則不適合使用，len會過大，導致使用過多記憶體空間，造成效率過低。

	int* twoSum(int* nums, int numsSize, int target) {
	//int可表達有號最大正整數值為2147483647，此處可得到數組最小值min
	int min = 2147483647;
	int i = 0;
	for( i = 0; i < numsSize; i ++)
	{
	if( nums[i] < min ) min = nums[i];
	}
	//target為兩數相加，扣掉min後，另一解為max(不可能比max大)
	int max = target - min;
	//len為hash長度，最差情況是max到min之間的數都相差1
	//意義為從min開始往後找len個數值以內，一定可以找到max為解
	int len = max - min + 1;
	int *ans = (int*)malloc(2*sizeof(int));
	int *table = (int*)malloc(len*sizeof(int));
	//初始化table，因為不保證每一格都會用到，避免不可預期的錯誤
	for (i = 0; i < len; i++) {
	table[i] = -1;
	}
	for( i = 0; i < numsSize; i++)
	{
	//不需考慮比max大的解
	if( nums[i] < max + 1 )
	{
	//target-min=另一解的最大值，再-nums[i]後，若查表得知table已更動過
	//表示此解已被尋訪過，就找到解答了
	if( table[target - min - nums[i]] != -1)
	{
	ans[0] = table[target - min - nums[i]];
	ans[1] = i;
	return ans;
	}
	//若查表得知table未更動過，表示此解尚未被尋訪，則修改table值
	table[nums[i] - min] = i;
	}
	}
	return ans;
	}

view raw TwoSum solution2 hosted with ❤ by GitHub
註：c資料型態表達範圍
3. Hash Table(C++ STL : map)：

	class Solution {
	public:
	vector<int> twoSum(vector<int>& nums, int target) {
	vector<int> ans;
	//使用C++ STL的map來實作Hash table
	map<int, int> table;
	map<int, int>::iterator iter;
	//尋訪一遍數組
	for( int i = 0; i < nums.size(); i++ )
	{
	//同2.之觀念，尋訪到nums[i]時，若 target - nums[i] 不在 Hash Table中
	//則更新hash table(nums[i], i)。反之，可得到另一解
	iter = table.find(target - nums[i]);
	if(iter != table.end())
	{
	ans.push_back(iter->second);
	ans.push_back(i);
	return ans;
	}
	else
	table.insert( pair<int,int>(nums[i] , i) );
	}
	return ans;
	}
	};

view raw TwoSum solution3 hosted with ❤ by GitHub
註:C++ STL(map)介紹