学步园

/*******************************************************************************************************************************************
3.找出两个数组中满足给定和的数对
问题描述：有两个数组arr1和arr2，两个数组均已经排好序，现在要找出这样的x和y使得x+y=sum，其中sum已知，x是arr1中某个元素，y是arr2中的某个元素。
解决方案：既然数组arr1和arr2中的元素已经排好序了，那么问题就简单了不少。假设arr1[i] + arr2[j] > sum，若arr1下标不变，那么要找到满足条件的x和y，
只能取arr2中下标< j 的元素和arr1[i]相加，结果才可能等于sum；假设arr1[i] + arr2[j] < sum，若arr2的下标不变，那么要找到满足条件的x和y，
只能取arr1中下标 > i 的元素和arr2[j]相加，结果才可能等于sum。因此我们可以设置两个指针 i 和 j ，分别指向arr1的开始位置和arr2结束位置，
这时 i 只能不断变大，j 只能不断变小，直到超过了数组的范围。通过代码更好理解，看代码吧~~时间复杂度是O(n+m)，n和m分别是arr1和arr2的大小。
************************************************************************************************************************************************/

bool getthesum(int arr1[], int arr2[], int length1, int length2, int sum)
{
	bool find = false;
	int i = 0;
	int j = length2 - 1;
	while( i < length1 && j >= 0)
	{
		if (arr1[i] + arr2[j] < sum)
		{
			i++;
		}
		else if(arr1[i] + arr2[j] > sum)
		{
			j--;
		}
		else if(arr1[i] + arr2[j] == sum)
		{
			find = true;
			printf("arr1[%d]=%d and arr2[%d]=%d equals to %d\n", i, arr1[i], j, arr2[j], sum);
			i++;
			j--;
		}
	}
	return find;
}




int _tmain(int argc, _TCHAR* argv[])
{
	int arr1[7] = {1, 2, 3, 4, 5, 6, 7};
	int arr2[7] = {3, 4, 5, 6, 7, 8, 9};
	getthesum(arr1, arr2, 7, 7, 12);
	getchar();
	return 0;
}