1組の数に複数の数の和が存在するかどうかは既知数に等しい

1172 ワード

1.2つの数の和が既知数(key)と等しいかどうか.
A:窮挙:配列中に2つの数を選択する、既知数、複雑度O(N^2)に等しいか否かを判断する.
B:二分:まず並べ替え(秩序がある場合は不要)、次に二分してM-array[i]がこの配列に存在するかどうかを調べ、複雑度O(N*log(N)).
C:まず並べ替え(秩序がある場合は不要)、次に2つのポインタ(ヘッドポインタheadとテールポインタtail)を用いて、*head+*tail>keyの場合、tail--、小さい場合はhead++であり、等しい場合は存在する.
Cの場合:
int getResult(int *num, int n_len, int key, int &num_1, int &num_2) {

	int *i, *j;

	int temp;

	i = num, j = num + n_len - 1;

	while (i < j) {

		temp = *i + *j;

		if (temp > key) {

			j--;

		} else if (temp < key) {

			i++;

		} else {

			num_1 = *i;

			num_2 = *j;

			return true;

		}

	}

	return false;

}



public static void getResult(int[] num_Array, int len, int key) {

		int i, j, temp;

		i = 0;

		j = len - 1;

		while (i < j) {

			temp = num_Array[i] + num_Array[j];

			if (temp > key) {

				j--;

			} else if (temp < key) {

				i++;

			} else {

				System.out.println(num_Array[i] + " " + num_Array[j]);

				return;

			}

		}

	}


練習:SOJ SUM http://cs.scu.edu.cn/soj/problem.action?id=1627