數字之魅：快速尋找滿足條件的兩個數

能否快速找出一個數組中的兩個數字，讓這兩個數字之和等於一個給定的數字，為了簡化起見，我們假設數數組中肯定存在這樣一組以上符合要求。

這個題目看起來其實並不難，但是仔細想想還是有許多值得思考的地方。

方案一：常人常規蠻力法。窮舉法，需要找數據我們就挨個找，總是能找出來，就是時間問題，我麼一次列舉每一個數和後一個數的和看是否與目標值相等。但是其時間復雜度為O(N*N)。

方案二：由於是查找，我們就可以對其進行排序操作，先排序再查找。為什麼要排序呢?這裡可以將問題轉化一下?既然是尋找和為Sum的兩個數，那麼我們就可以查找Sum-arr[i]是否在數組中，在排序後我們就可以使用我們非常熟練的二分查找算法，這樣查找一個數據的時間復雜度就降低到了O(logN)，但是需要對每一個元素都需要查找，所示其實時間復雜度為O(N*logN)。另外對數據進行排序，我們可以知道其時間復雜度為O(N*logN)，綜合其時間復雜度為：O(N*logN)。

方案三：時間換空間的方法。我們采用一個hash表將所有的數據映射到表中，然後Sum-arr[i]只需要O(N)的時間久可以了，這樣的話，其時間復雜度就被我們降低到了O(N)+O(N)的輔助空間。

方案四：基於求一個整數的所有連續的有序序列的啟發，我們可以先對數組進行排序，時間復雜度為O(N*logN)，然後對於給定的Sum，i=0,j=N-1,我們首先看arr[i]+arr[j]是否等於Sum，如果小於則i++;否則j--，這樣在O(N)的時間復雜度就可以完成。綜合總的時間復雜度為：O(N*logN)。

方案四實現代碼：
 

void Find(int *arr,int *data1,int *data2,int lenght,int Sum)
{
	int i,j;
	for(i=0;j<lenght;i<j)
	{
		if(Sum==arr[i]+arr[j])//找到了；
		{
			*data1=arr[i];//記住這兩個數；
			*data2=arr[j];
		}
		else if(arr[i]+arr[j]<Sum)
			i++;
		else
			j--;
	}
}