Задачка на массивы

@olderprogrammer · Регистрация: 20.07.2021

Студворк — интернет-сервис помощи студентам

Всем привет, есть задача на массивы, честно говоря даже не знаю с чего начинать, помогите пожалуйста решением

Дан массив с int переменными, определить количество пар, разность которых эквивалентна заданному с консоли target значению.
Например, дан массив чисел [1,2,3,4] и введенное с консоли target значение 1, у нас есть три пары, которые подходят под заданное условие: 2-1=1, 3-2=1, 4-3=1.
Нужно дописать код в pairs функции, которая принимает массив int значений и target int переменную, которая бы возвращала количество пар с заданной разностью.
Параметры:
• k: int, target переменная, разница
• arr: массив int значений
Формат ввода:
• Первая строка принимает 2 значения отделенных пробелом, размер массива arr и target значение. (n и k)
• Вторая строка содержит n отделенных друг от друга int значений массива arr.
Ограничения:
• каждое значение arr[i] должно быть уникальным

Формат вывода:
Целочисленное число, отображающее количество пар, разность которых равна k (target переменной)
Пример ввода:
5 2
1 5 3 4 2
Пример вывода:
3

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
///////////////////////////////////////////////////////////////////////////////
public class Solution {
 
    // Complete the pairs function below.
    static int pairs(int k, int[] arr) {
        int pairsCount = 0;
        // write code here
        return pairsCount;
    }
 
    private static final Scanner scanner = new Scanner(System.in);
 
    public static void main(String[] args) throws IOException {
 
        String[] nk = scanner.nextLine().split(" ");
 
        int n = Integer.parseInt(nk[0]);
 
        int k = Integer.parseInt(nk[1]);
 
        int[] arr = new int[n];
 
        String[] arrItems = scanner.nextLine().split(" ");
 
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(arrItems[i]);
            System.out.println(arr[i]);
        }
 
        int result = pairs(k, arr);
        System.out.println(result);
 
        scanner.close();
    }
} 

@xoraxax · 20.07.2021, 20:44

Сообщение от Coffeini

Так или иначе, в худшем случае будет O(nlogn), что все еще лучше O(n^2).

ну в целом да )

@Arsegg · 20.07.2021, 22:05

Сообщение от Coffeini

в худшем случае будет O(nlogn), что все еще лучше O(n^2).

В худшем случае тоже будет O(N ^ 2), при условии, что коллизий в каждом бакете <= 6 (или 8). Не помню, при каком количестве коллизий бакет перестраивается в RBT.

@Coffeini · 20.07.2021, 22:25

Как может быть O(n^2), если поиск будет занимать ну максимум 8^2? Ну т.е. O(n*8^2), что является константой, а потому можно упростить до O(n). Как я понимаю худший случай, это когда в одном бакете собрались все элементы. Но теперь-то это будет O(logn).
Хотя я могу заблуждаться. Да и рассуждения ушли далеко от изначальной темы.

Новые блоги и статьи Все статьи Все блоги /
Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .

@Coffeini 753 / 370 / 133 Регистрация: 01.02.2020 Сообщений: 1,096 Записей в блоге: 1
	20.07.2021, 22:25
	Как может быть O(n^2), если поиск будет занимать ну максимум 8^2? Ну т.е. O(n*8^2), что является константой, а потому можно упростить до O(n). Как я понимаю худший случай, это когда в одном бакете собрались все элементы. Но теперь-то это будет O(logn). Хотя я могу заблуждаться. Да и рассуждения ушли далеко от изначальной темы. 0