編程之美2.12 快速尋找滿足條件的兩個數

編程之美2.12 快速尋找滿足條件的兩個數

這道題目的意思是，在一個數組中尋找兩個數，使這兩個數的和等於給定的數（找到任意一組就可以了）。

題目讀完之後，感覺這道題目還是很簡單的，就是遍歷數組呗，走兩遍，即可以在O(n2)時間復雜度內解決這個問題。不過，仔細想想之後，復雜度還是可以降低的。

首先，我們可以對數組進行排序，這樣，得到的數組就是一個有序數組（假設數組是遞增的），那麼，我們可以利用兩個指針，一個指針指向數組的第一個元素，一個指針指向數組的最後一個元素，所以，就是兩個指針分別指向兩個最值。然後前後每次移動一個指針就可以嘗試的去尋找所需要的一組數。

比如，初始時，兩個指針指向的值相加之後，和大於給定的數字，那麼，就需要把“最大值指針”向前移動，這樣，就會使得兩個指針指向的值的和變小；如果兩個指針指向的值相加小於給定的數字，那麼，就需要把“最小值指針”向後移動，這樣，就會使得兩個指針指向的值的和變大了，然後，終止條件是兩個指針不能相等或者“最小值指針”等於“最大值指針”。

有了上述思想，可以得到如下的解決辦法：

函數聲明：

/*2.12 快速尋找滿足條件的兩個數*/
void DutQuickFindSpecifyTwoNums(int*, int, int, int&, int&);

源代碼：

/*快速尋找兩個值*/
bool _DutQuickFindSpecifyTwoNums = false;
void DutQuickFindSpecifyTwoNums(int* A, int size, int sum, int& one, int& two)
{
	if (!A || size <= 1)
	{
		one = -1;
		two = -1;

		return;
	}

	std :: sort(A, A + size);

	int i = 0;
	int j = size - 1;

	/*即前後各一個指針，然後兩個指針往中間方向走，比對遇到的值*/
	while (i < j)
	{
		if (A[i] + A[j] == sum)
		{
			one = A[i];
			two = A[j];

			return;
		}
		else if (A[i] + A[j] > sum)
			--j;
		else
			++i;
	}

	one = -1;
	two = -1;

	return;
}