w
Не так стыдно оквадратиться как окубиться)
Ме вариант Игоря нравится больше
Size: a a a
2019 October 11
IE
В смысле? Там все ок вроде бы
при j = i он берет первое число допустим 1 и суммирует его с arr[j] которое тоже будет 1
AK
при j = i он берет первое число допустим 1 и суммирует его с arr[j] которое тоже будет 1
А ну да, второй цикл должен идти от следующего элемента массива
IE
ага
IE
Ме вариант Игоря нравится больше
который? ))) я уже потерялся
AK
Так превращаем n^2, в n*log(n); что и будет финальной сложностью
w
h ={}
ar.each_with_index do |i, a|
ar[i, -1].each do |b|
sum = a+b
h[sum] ||= 0
h[sum] += 1
end
end
h.keys.select{|k| h[k] == 1}w
ага
w
схематично
AK
Не нужен последний селект
AK
Лишняя итерация
w
почему ?
МК
Лишняя итерация
Уникальные суммы не найти иначе
AK
Внутри внутреннего цикла нужно сделать array << sum if h[sum] == 1
AK
Этого будет достаточно и избавляет от лишнего прохода
w
и удалять если уже больше?
w
сложность будет выше, чем лишний раз пробежаться
МК
Внутри внутреннего цикла нужно сделать array << sum if h[sum] == 1
Эмм, пока последний цикл внутренний не пройдет, не будет известно, точно ли h[sum]==1
AK
Нет, мы заводим hashmap для провероки и дополнительный массив для результата
w
ну вот я считаю, получаю сумму 5