10126. Пары

Задан массив различных целых чисел и число k. Определите количество пар элементов массива, разница которых равна k.

Вход. Первая строка содержит два целых числа n (2 ≤ n ≤ 10⁵) и k (0 < k < 10⁹). Вторая строка содержит n различных целых чисел в промежутке от 0 до 2³¹ – 1.

Выход. Выведите количество пар чисел массива с разностью k.

Пример входа	Пример выхода
6 3 7 3 5 1 10 2	2

РЕШЕНИЕ

множество

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

Занесем все числа во множество s. Далее перебираем элементы множества и для каждого его значения x проверяем, содержится ли во множестве число x + k. Подсчитываем количество таких пар x и x + k, для которых оба числа принадлежат множеству.

Пример

Рассмотрим вид множества в результате сортировки:

На расстоянии k = 3 находится две пары элементов: (2, 5) и (7, 10).

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

Читаем входные данные. Читаем входной массив во множество s.

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

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

{

scanf("%d", &x);

s.insert(x);

}

Количество искомых пар подсчитываем в переменной res.

res = 0;

Перебираем элементы множества. Для каждого значения x из s проверяем, содержится ли в s число x + k. Если содержится, то увеличиваем значение res.

for (int x : s)

if (s.find(x + k) != s.end()) res++;

Выводим ответ.

printf("%d\n", res);

Java реализация

import java.util.*;

public class Main

{

public static void main(String []args)

{

Scanner con = new Scanner(System.in);

TreeSet<Integer> s = new TreeSet<Integer>();

int n = con.nextInt();

int k = con.nextInt();

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

{

int x = con.nextInt();

s.add(x);

}

int res = 0;

for(int x : s)

if (s.contains(x + k)) res++;

System.out.println(res);

con.close();

}

}