11244. Сумма двух

 

Задан массив A, отсортированный по возрастанию и содержащий n целых чисел. Определите, существует ли в нем такая пара чисел (Ai, Aj), i < j, сумма которых равна x.

 

Вход. Первая строка содержит два целых числа n (n ≤ 105) и x (x ≤ 106). Вторая строка содержит n целых неотрицательных чисел, каждое из которых не больше 106.

 

Выход. Выведите “YES” если такая пара элементов существует, и “NO” иначе.

 

Пример входа 1

Пример выхода 1

10 13

1 3 5 6 8 10 11 11 11 16

YES

 

 

Пример входа 2

Пример выхода 2

8 61

5 5 8 12 16 21 44 50

NO

 

 

РЕШЕНИЕ

два указателя

 

Анализ алгоритма

Пусть v – входной массив чисел. Инициализируем указатели i = 0 на начало массива, j = n – 1 на конец массива. Массив по условию задачи уже отсортирован.

Пока указатели i и j не встретятся, совершаем следующие действия:

·        Если v[i] + v[j] = x, то искомая пара элементов найдена, выводим ее и завершаем программу.

·        Если v[i] + v[j] < x, то двигаем указатель i на одну позицию вправо. В этом случае сумма v[i] + v[j] будет увеличиваться;

·        Если v[i] + v[j] > x, то двигаем указатель j на одну позицию влево. В этом случае сумма v[i] + v[j] будет уменьшаться;

 

Пример

Рассмотрим первый тест. Инициализируем указатели. Промоделируем работу алгоритма. Значение x = 13, ищем два числа с суммой 13.

 

 

Реализация алгоритма

Читаем входные данные.

 

scanf("%d %d", &n, &x);

v.resize(n);

for (i = 0; i < n; i++)

  scanf("%d", &v[i]);

 

Инициализируем указатели. 

 

int i = 0, j = v.size() - 1;

 

Указатель i двигаем вперед, указатель j двигаем назад.

 

while (i < j)

{

 

Если v[i] + v[j] = x, то искомая пара элементов найдена. Выводим ее и завершаем программу.

 

  if (v[i] + v[j] == x)

  {

    printf("YES\n");

    return 0;

  }

 

Если v[i] + v[j] < x, то двигаем указатель i на одну позицию вправо;

Если v[i] + v[j] > x, то двигаем указатель j на одну позицию влево;

 

  if (v[i] + v[j] < x) i++; else j--;

}

 

Если искомая пара не найдена, то выводим “NO”.

 

printf("NO\n");

 

Java реализация

 

import java.util.*;

 

public class Main

{

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    int n = con.nextInt();

    int x = con.nextInt();

    int v[] = new int[n];

    for(int i = 0; i < n; i++)

      v[i] = con.nextInt();

 

    int i = 0, j = n - 1;

    while (i < j)

    {

      if (v[i] + v[j] == x)

      {

        System.out.println("YES");

        return;

      }

      if (v[i] + v[j] < x) i++; else j--;

    }

    System.out.println("NO");

    con.close();

  }

}

 

Python реализация

Читаем входные данные.

 

n, x = map(int,input().split())

lst = list(map(int,input().split()))

 

Инициализируем указатели. 

 

i = 0

j = n – 1

 

Указатель i двигаем вперед, указатель j двигаем назад.

 

while (i < j):

 

Если v[i] + v[j] = x, то искомая пара элементов найдена. Выводим ее и завершаем программу.

 

  if (lst[i] + lst[j] == x):

    print("YES")

    exit()

 

Если v[i] + v[j] < x, то двигаем указатель i на одну позицию вправо;

Если v[i] + v[j] > x, то двигаем указатель j на одну позицию влево;

 

  if (lst[i] + lst[j] < x):

    i += 1

  else:

    j -= 1

 

Если искомая пара не найдена, то выводим “NO”.

 

print("NO")