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;
}