【算法】检测数组里是否有两个数之和等于某个数

问题:
检测数组里是否有两个数之和等于某个数

解决方法一:先将数组排序,然后从两头开始遍历
数组排序后,从左端开始取最小值,从右端取最大值,
判断两者之和与目标的大小:

  1. 等于时,输出两个数;
  2. 大于时,右端移到第2个数,继续判断;
  3. 小于时,左端移到第2个数,继续判断。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

void fun1(int a[], int length, int target) {
	// 给数组排序
	sort(a, a + length);
	// left是最小值,right是最大值
	int left = 0, right = length - 1;
	while (left < right) {
		int tmp = a[left] + a[right];
		if (tmp == target) {
			cout << a[left] << a[right] << endl;
			return;
		}
		else if (tmp > target) { // 和比目标大,就减小right,从而减小和
			right--;
		}
		else {	// 和比目标小,就增大left,从而增大和
			left++;
		}
	}
	cout << "无" << endl;
}

int main() {
	int a[] = {
		1, 3, 2, 7, 6, 9, 8, 0, 5, 4
	};

	int target = 0;
	while (cin >> target) {
		fun1(a, 10, target);
	}
}


上述方法虽然简单,但弊端也有,没法输出所有等于目标值的两个数。

解决方法二
暴力解法,记录下每一个数与其他数的和放在一个二维数组里,然后遍历即可,这样可以记录下所有的和等于目标值的数值对,如下:
假设输入数组为: 2 3 4 5 1
有如下矩阵:

 ==2====3====4====5====1==
==2==- 5 6 7 3
==3==5 - 7 8 4
==4==6 7 - 9 5
==5==7 8 9 - 6
==1==3 4 5 6 -
当目标值为7时,就有两组: (5,2)与(3,4) 考虑到对称性,有n[i][j] = n[j][i],i!=j, ,所以,我们只需要i>j的数值对就行。
void fun2(int a[], int length, int target) {
	int** n = new int*[length];
	for (int i = 0; i < length; i++) {
		n[i] = new int[length];
	}
	for (int i = 0; i < length; i++) {
		for (int j = length - 1; j > i; j--) {
			n[i][j] = n[j][i] = a[i] + a[j];
		}
	}
	for (int i = 0; i < length; i++) {
		for (int j = length - 1; j > i; j--) {
			if (n[i][j] == target) {
				cout << a[i] << " " << a[j] << endl;
			}
		}
	}
	
}