首页 > 代码库 > 编程之美2.12 高速寻找满足条件的两个数

编程之美2.12 高速寻找满足条件的两个数

      这道题目的意思是,在一个数组中寻找两个数。使这两个数的和等于给定的数(找到随意一组就能够了)。

      题目读完之后,感觉这道题目还是非常easy的。就是遍历数组呗,走两遍,即能够在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;
}


编程之美2.12 高速寻找满足条件的两个数