Вопрос по задаче D "Три числа"

Как можно определить, существует ли в массиве из N целых чисел три числа, сумма которых равна нулю?

Формат входных данных

В первой строке входного файла указано одно целое число N (1 ≤ N ≤ 2000). Во второй строке находятся N целых чисел a1, a2, ..., aN ( - 1000 ≤ ai ≤ 1000) — элементы массива.

Формат выходных данных

В единственной строке выходного файла выведите одно слово «YES», если в этом массиве есть три числа, сумма которых равна нулю. В противном случае, выведите «NO».

Решите задачу на C++!

Информатика 11 класс Алгоритмы и структуры данных определение трех чисел сумма равна нулю задача D массив целых чисел алгоритм на C++ входные данные выходные данные программирование информатика 11 класс Новый

Для решения задачи о нахождении трех чисел в массиве, сумма которых равна нулю, можно использовать алгоритм с сортировкой и двумя указателями. Этот метод эффективен и позволяет проверить условие за время O(N^2). Давайте разберем шаги решения подробно.

Шаги решения:

1. Считывание данных:
   • Сначала считываем количество элементов N.
   • Затем считываем массив целых чисел.
2. Сортировка массива:
   • Сортируем массив чисел. Это необходимо для удобства использования двух указателей.
3. Поиск тройки чисел:
   • Итеративно проходим по каждому элементу массива, используя его как первый элемент тройки.
   • Для оставшихся двух чисел используем два указателя: один указывает на элемент сразу после текущего, а другой — на последний элемент массива.
   • Сравниваем сумму трех чисел:
   • Если сумма равна нулю, выводим "YES".
   • Если сумма меньше нуля, перемещаем левый указатель вправо, чтобы увеличить сумму.
   • Если сумма больше нуля, перемещаем правый указатель влево, чтобы уменьшить сумму.
4. Вывод результата:
   • Если не нашли подходящую тройку, выводим "NO".

Теперь давайте посмотрим на реализацию на C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> a(N);

    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    for (int i = 0; i < N - 2; i++) {
        int left = i + 1;
        int right = N - 1;

        while (left < right) {
            int sum = a[i] + a[left] + a[right];
            if (sum == 0) {
                cout << "YES" << endl;
                return 0;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

    cout << "NO" << endl;
    return 0;
}

В этом коде мы сначала считываем размер массива и сами элементы. Затем сортируем массив и применяем метод с двумя указателями для поиска тройки чисел, сумма которых равна нулю. Если такая тройка найдена, программа выводит "YES", в противном случае — "NO".