Сравнение двух массивов без вложенных циклов

@vkiper · Регистрация: 11.11.2015

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

Извиняюсь, что помещаю здесь этот вопрос, я сам по идее должен был догадаться, но никак не могу. Второй день гружусь, без толку

Имеются два массива с числами(int), одного размера, скажем, в каждом массиве по 20 чисел, больше нуля. Например:

C++
1
2
array1[20] = { 2, 5, 3, 7, 9, 6, ....}
array2[20] = { 8, 4, 1, 6, 13, 21, ....}

Дано контрольное число 8. Нужно сопоставить два массива и выявить ближайший случай, когда число из первого и число из второго массива дадут в сумме эту восьмерку.
В данном случае это будет: array1[0] + array2[3] = 8 // 2 + 6 = 8
Стандартное решение подразумевает цикл в цикле, т.е. сложность алгоритма будет N*N, если за N мы берем размер массива.
Меня попросили найти более простое решение, без вложенных циклов. Догадываюсь, что где-то в сети или в учебниках оно разжевано, но не могу найти.
Всем 10х

@vantfiles · 17.02.2022, 02:42

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

Доступ к сету О(1). То есть, затраты времени линейно зависят от размера.

???

Добавлено через 47 секунд
O(1) можно прочитать как «сложность порядка 1» (order 1), или «алгоритм выполняется за постоянное/константное время» (constant time).

@Mikhaylo · 17.02.2022, 06:20

Доступ к множеству или словарю за O(1) - это несколько ложная информация. Я бы раскрыл механизм доступа и увидел там сложность от O(1) до O(n) в лучшем и худшем случае. Я бы лучше прямо здесь говорил не о множестве или словаре, а о хэшировании, потому что это существенная часть алгоритма для задачи, не то, что скрывающая его запись "b in A".
А вот доступ к массиву за O(1) - это более серьезно.

@Shamil1 · 17.02.2022, 22:27

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

???

Описка. Затраты времени не зависят от размера.

Новые блоги и статьи Все статьи Все блоги /
Особенности 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 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .

@Mikhaylo 821 / 580 / 75 Регистрация: 20.09.2014 Сообщений: 3,827
	17.02.2022, 06:20
	Доступ к множеству или словарю за O(1) - это несколько ложная информация. Я бы раскрыл механизм доступа и увидел там сложность от O(1) до O(n) в лучшем и худшем случае. Я бы лучше прямо здесь говорил не о множестве или словаре, а о хэшировании, потому что это существенная часть алгоритма для задачи, не то, что скрывающая его запись "b in A". А вот доступ к массиву за O(1) - это более серьезно. 0