Ну я бы сказал, что есть много подходов к решению подобных задач. Там надо отталкиваться от конкретной задачи. Вот к примеру даже взять вашу задачу.
Дано:
длина первого массива: n
длина второго массива: m
Можно решать в лоб, и полным перебором циклом в цикле просматривать все элементы, для каждого элемента из первого цикла проходить по всем элементам второго цикла и смотреть на результат.
first_arr = [1, 3, 2, 9, 5, 2, 3, 1, 4, 1, 0, -1, -2, -4, 2, 3, 10, 12, -9]
second_arr = [5, 2, 1, 0, -2, -3, 4, 5, -10, -9, -2, -6, 8, 12, 34, 3, 9, 19]
result = 0
for i in first_arr:
for j in second_arr:
if i + j == 2:
result += 1
print(result)
В таком случае количество операций будет не меньше n * m
.
Можно заметить, что, если мы отсортируем второй массив за O(n*log(n))
, то нам будет легче искать элементы в нем. Тогда пройдясь по всем элементам первого массива мы с помощью бинарного поиска сможем найти элемент, дополняющий его в сумме до 2. Ну или сказать, что такового нет. Бинарный поиск это O(log(n))
и как итог получится O(n*log(n) + n*log(m))
. Ну это получше конечно чуть чуть, но далеко от идеала.
Если известно, что в массивах нет дублирующихся элементов (в одном массиве двух одинаковых), то можно вспомнить про set
, который основан на хэш-функции и строится за O(n)
. Тогда мы строим множество из одного из списков за O(n)
(или O(m)
), и проидясь по массиву определим, есть ли в множестве дополняющий до 2 элемент. Так как используются хэш-функции доступ будет за O(1)
.
first_arr = [1, 3, 2, 9, 5, 4, 0, -1, -2, -4, 10, 12, -9]
second_arr = [5, 2, 1, 0, -2, -3, 4, -10, -9, -6, 8, 12, 34, 3, 9, 19]
result = 0
set_from_second_arr = set(second_arr)
for i in first_arr:
if (2 - i) in set_from_second_arr:
result += 1
print(result)
Общая сложность примерно O(n + m)
(построение множества - O(n)
, обход списка O(m)
).
Если вдруг элементы повторяются, да и такое бывает. Тогда можно вспомнить про Counter
, можно его и самому написать, он работает на словарях. Там сложность его построения тоже примерная O(n)
. Тут отличие от предыдущего алгоритма только в том, что мы прибавлять будем не 1 к результату, а количество повторений подходящего нам дополняющего числа.
from collections import Counter
first_arr = [1, 3, 2, 9, 5, 4, 0, -1, -2, -4, 10, 12, 12, 12, -9]
second_arr = [5, 2, 1, 1, 0, -2, -2, -2, -3, 4, -10, -10, -10, -9, -6, 8, 12, 34, 3, 9, 19]
result = 0
dictionary_from_second_arr = Counter(second_arr)
for i in first_arr:
if (2 - i) in dictionary_from_second_arr:
result += dictionary_from_second_arr[(2 - i)]
print(result)
Ну примерно так, много разных подходов к решению задач.