LeetCode 523. 连续的子数组和(前缀和)

本文主要是介绍LeetCode 523. 连续的子数组和(前缀和)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.题目

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

• 子数组大小 至少为 2 ，且
• 子数组元素总和为 k 的倍数。

如果存在，返回 true ；否则，返回 false 。

如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。

 

示例 1：

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

示例 2：

输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。 
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。

示例 3：

输入：nums = [23,2,6,4,7], k = 13
输出：false

提示：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9
• 0 <= sum(nums[i]) <= 2^31 - 1
• 1 <= k <= 2^31 - 1

 2.思路

(1)连续子数组的和不难想到要求nums的前缀和

(2)本题的难点是如何使连续子数组的和为k的倍数，即子数组对k取余需为0，暴力搜索所有子数组的情况必然会超时，所以此时需要利用余数的性质，如下图：

 3.代码

class Solution:def checkSubarraySum(self, nums: List[int], k: int) -> bool:n = len(nums)arr = nums[:]"""储存余数,并进行初始化"""mp = {0}for i in range(1, n):arr[i] += arr[i - 1]"""如果arr[i]的余数在[0,i-2]中出现过则返回True"""if arr[i] % k in mp:return Truemp.add(arr[i - 1] % k)return False

 

 

这篇关于LeetCode 523. 连续的子数组和(前缀和)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---