16-寻找指定和的整数对

1、问题描述

例题：寻找指定和的整数对

输入 n ( n<= 100,000)个整数，找出其中的两个数，它们之和等于整数 m (假定肯定有解)。题中所有整数都能用 int 表示

2、问题分析

首先想到最简单的用两重循环，枚举所有的取数方法，复杂度是O(n2)的。

for(int i = 0;i < n-1; ++i)
	for(int j = i + 1; j < n; ++j)
		if( a[i]+a[j] == m)
			break;
           

100,0002 = 100亿，这个计算量太大了，一定会超时的，一般10亿一定会超时，1亿，几千万可能通过，几百万一定能通过。

方法1：

1. 将数组排序，复杂度是 O(n×log(n))
2. 对数组中的每个元素 a[i]，在数组中二分查找 m-a[i]，看能否找到。复杂度 log(n)，最坏要查找 n-2 次，所以查找这部分的复杂度也是O(n×log(n))

这种解法总的复杂度是 O(n×log(n)) 的。

#include<iostream>
#include<algorithm>
using namespace std;
typedef int ElementType;

void sumofnum(ElementType a[], int len, ElementType expectsum)
{
	sort(a, a + len - 1);
	for (int i = 0; i < len; i++)
	{
		int left = i+1, right = len - 1;
		while (left <= right)
		{
			int mid = left + (right-left) / 2;
			if (a[i] + a[mid] > expectsum)
				right = mid - 1;
			else if (a[i] + a[mid] < expectsum)
				left = mid + 1;
			else
			{
				cout << a[i] << "\t"<< a[mid] << endl;
				break;
			}
		}

	}
}

int main()
{
	int a[] = { 2, 4, 6, 1, 0, 8, 10, 3, 5, 12, 14, 16, 18 };
	int len = sizeof(a) / sizeof(a[0]);
	sumofnum(a, len, 18);	
	return 0;
}
           

方法2：

1. 将数组排序，复杂度是 O(n×log(n))
2. 查找的时候，设置两个变量 i 和 j，i 初值是0，j 初值是 n-1，看 a[i]+a[j]，如果大于 m，就让 j 减1，如果小于 m，就让 i 加1，直至 a[i]+a[j]=m。

这种解法总的复杂度是O(n×log(n))的。

#include<iostream>
#include<algorithm>
using namespace std;
typedef int ElementType;

void sumofnum(ElementType a[], int len, ElementType expectsum)
{
	if (a == NULL || len == 0)
		return;
	sort(a, a + len - 1);
	int left = 0, right = len - 1;//左右下标指向头和尾
	while (left<right)
	{
		int sum = a[left] + a[right];
		if (sum > expectsum)
			right--;
		else if (sum < expectsum)
			left++;
		else
		{
			cout << a[left] << "\t" << a[right] << endl;
			left++;
			right--;
		}
	}
}
int main()
{
	int a[] = { 2, 4, 6, 1, 0, 8, 10, 3, 5, 12, 14, 16, 18 };
	int len = sizeof(a) / sizeof(a[0]);
	sumofnum(a, len, 18);
	return 0;
}