#python #sub-array
#питон #подрешетка
Вопрос:
Я столкнулся с этой проблемой, когда мне нужно проверить, существует ли сумма подмассива, кратная целевому значению, и если длина подмассива составляет не менее 2.
Я посмотрел на одно из решений, которое приведено ниже
class Solution(): def checkSubarraySum(self, nums, k): """ :type nums: List[int] :type k: int :rtype: bool """ dic = {0:-1} summ = 0 for i, n in enumerate(nums): if k != 0: summ = (summ n) % k else: summ = n if summ not in dic: dic[summ] = i else: if i - dic[summ] gt;= 2: return True return False
Чего я не понимаю, так это почему «i — dic[сумма] gt;= 2» вместо большего или равного 1? Я предполагаю, что он проверяет, больше ли длина 2, так что не будет ли разница между двумя индексами плюс один равна длине подмассива?
Комментарии:
1. Он сравнивает расстояние между двумя индексами, чтобы увидеть, равно ли оно хотя бы 2. Тем не менее, реализация алгоритма может быть или не быть правильной (я не знаю).
Ответ №1:
Поскольку все элементы в nums
являются либо 0, либо положительными, условие summ in dic
(иначе summ not in dic
) и i - dic[summ] gt;= 2
выполняется только тогда, когда строка summ = (summ n) % k
выполняется в одной и той же итерации. Причина, по которой нам нужно проверить, почему это gt;=2
так, а не gt;=1
иначе, заключается в том, что индекс in dic[summ]
не включен в подмассив, поэтому i - dic[summ]
необходимо проверить, равен ли размер непрерывного подмассива не менее 2