Это проблема, которую мой друг получил в качестве домашней работы (в алгоритме и классе структуры данных). Он спросил меня об этом. Однако я не могу решить эту проблему и думал об этом в течение нескольких последних дней.
В диапазоне [0, 2 31 -1] есть n случайных целых чисел (могут быть дубликаты. Определите, удовлетворяют ли 3 номерам этих чисел A + B = C.
Сначала я придумал наивный алгоритм, что O (n 2 log n). Затем я придумал алгоритм, что O (n 2). Вот псевдокод:
sort(a); // non-descending
for (i = 0; i < n; i++) {
j = i; k = i + 1;
while (j < n && k < n) {
if (a[i] + a[j] == a[k])
return true;
else if (a[i] + a[k] < a[j])
k++;
else
j++;
}
}
return false;
Однако проблема заключается в том, что 1 < n <= 10 6. Я считаю, что O (n 2) слишком медленный. Мое решение не использует случайность. Однако я не уверен, что это важная часть проблемы.