给定一数组,输出满足2a=b(a,b代表数组中的数)的数对,要求时间复杂度尽量低。

时间:2021-06-01 17:07:01
//时间复杂度O(n),空间复杂度O(n)
void findSequence(int* arr, int len) {
	int* hashtable = new int[RANGE];
	memset(hashtable, 0, RANGE);

	for (int i = 0; i < len; ++i) {
		hashtable[arr[i]] = 1;
	}

	cout << "(a,b): ";
	for (int i = 0; i < len; ++i) {
		if (arr[i] * 2 < len && hashtable[arr[i] * 2]) {
			//去重
			hashtable[arr[i]] = 0;
			cout << "( " << arr[i] << " , " << arr[i] * 2 << " ) ";
		}
		if (i % 10 == 0) {
			cout << endl;
		}
	}
}