python - 如何查找是否存在重叠子结构

Question

我目前正在做一个任务：

给定一个整数数组 nums 和一个整数 k，如果 nums 有一个大小至少为 2 且元素总和为 k 的倍数的连续子数组，则返回 true，否则返回 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？

注意：我知道这个问题的前缀和解决方案。

标签： pythonrecursion