Привет мир!
Приступим к задаче Шерлок и Массив на HackerRank. Вы можете нажать на заголовок, чтобы прочитать описание проблемы. Итак, начнем…
Задача состоит в том, что нам дан список A длины n, и нам нужно найти такой индекс i, что сумма элементов в его левой части равна сумме элементов в его правой части. Нам нужно напечатать «YES», если такой i существует, иначе нам нужно напечатать «NO».
Давайте попробуем тривиальный подход: мы можем выполнить итерацию от индекса i+1 до n-2, разбить список на два временных списка, найти сумму этих двух списков и сравнить, совпадают они или нет. Это довольно простой подход, и он уверен, что он работает. Мы все еще можем придумать лучшее решение. Позвольте мне провести вас через это.
Рассмотрим весы.
Пусть i = 0 и j = n-1. Теперь поместите элемент с индексом i в левый баланс и индексом j в правый баланс. Если левый баланс тяжелее (т. е. сумма больше), уменьшите j и добавьте j-й элемент в правый баланс. Как только правый баланс станет тяжелее, уменьшите i и добавьте i-й элемент в левый баланс. Делайте это до i != j. Как только i становится равным j, вы можете проверить, равен ли левый баланс правому балансу или нет.
Другой способ, о котором я расскажу, использует только одну переменную для отслеживания равенства и является более эффективным. Инициализируйте переменную ans = 0, i = 0 и j = n-1. Теперь, если ans ≥ 0, вычесть j-й элемент из an и уменьшить j. В противном случае добавьте i-й элемент в an и увеличьте i. Запустите цикл до i != j. Как только i станет равным j, проверьте, равен ли an по-прежнему нулю или нет. Если да, выведите «YES», иначе «NO».
Открыт для предложений. Код для этой задачи на Python3 можно найти здесь.
Удачного кодирования…
