leetcode-523-连续的子数组和

问题描述

给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n * k，其中 n 也是一个整数。

示例 1：

输入：[23, 2, 4, 6, 7], k = 6
输出：True
解释：[2, 4] 是一个大小为 2 的子数组，并且和为 6。

示例 2：

输入：[23, 2, 6, 4, 7], k = 42
输出：True
解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。

说明：

数组的长度不会超过 10,000 。
你可以认为所有数字总和在 32 位有符号整数范围内。

解题思路

动态规划

Python 实现

class Solution(object):
    def checkSubarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        d = []
        for i in range(len(nums)):
            d.append([None for _ in range(len(nums))])
            for j in range(i, len(nums)):
                if i == j:
                    d[i][j] = nums[i]
                else:
                    d[i][j] = d[i][j - 1] + nums[j]

                    if d[i][j] == 0 and k == 0:
                        return True

                    if k != 0 and d[i][j] % k == 0:
                        return True

        return False