#python #recursion
Вопрос:
В настоящее время я работаю над заданием:
Учитывая целочисленный массив nums и целое число k, возвращайте true, если nums имеет непрерывный подмассив размером не менее двух элементов, сумма которых кратна k, или false в противном случае.
Которую я решил с помощью следующего кода:
class Solution:
def helper(self,nums,k,crntsum,crntlen):
if crntsum % k==0 and crntlen>1:
return True
if len(nums)<=0:
return False
return self.helper(nums[1:],k,0,0) or self.helper(nums[1:],k,crntsum nums[0],crntlen 1)
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
return self.helper(nums,k,0,0)
На самом деле, это рекурсивный способ решения проблемы.
Есть ли какое-либо запоминание, которое можно сделать для этого? Если да, то как мы можем определить, что проблема имеет перекрывающиеся подзадачи. Можно ли для этого использовать DFS?
NB: Я знаю о решении этой проблемы с префиксной суммой.
Комментарии:
1. Это похоже на вопрос для интервью, и я не думаю, что ваше решение работает. Первая ветвь рекурсии в
orоператоре никогда не вернетсяTrue, потомуcrntlenчто всегда равна 0. Вторая ветвь продолжает прерываться в левой части массива, поэтому будет возвращенаTrueтолько для подмассива префикса, который удовлетворяет условию. Вы игнорируете подмассивы, которые не являются префиксамиnums(т. Е. Начинаются с серединыnums)2. Вы говорите, что знаете о префиксных суммах — так что запоминание как раз для вас. Суммы префиксов работают в линейное время (в худшем случае) с накладными расходами памяти
kили в квадратичное время , еслиkоно слишком велико и вы не хотите выделять дополнительную память. Не уверен, что еще вы ищете.