【LetMeFly】523.连续的子数组和

力扣题目链接：https://leetcode.cn/problems/continuous-subarray-sum/

给你一个整数数组 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 <= 105
• 0 <= nums[i] <= 109
• 0 <= sum(nums[i]) <= 231 - 1
• 1 <= k <= 231 - 1

方法一：哈希 + 前缀和

首先求出原始数组的前缀和prefixprefixprefix。prefix[i]=∑j=0j

求出前缀和有什么意义呢？如果我们想知道numsnumsnums数组从lll到rrr的和nums[l]+nums[l+1]+nums[l+2]+⋯+nums[r]nums[l] + nums[l + 1] + nums[l + 2] + \cdots + nums[r]nums[l]+nums[l+1]+nums[l+2]+⋯+nums[r]，那么我们就可以用前缀和数组prefix[r]−prefix[l−1]prefix[r] - prefix[l - 1]prefix[r]−prefix[l−1]在O(1)O(1)O(1)的时间复杂度内求出。

好了，现在我们来看题目，题目要找到是“是否存在numsnumsnums数组从lll到rrr的和，这个和是kkk的整数倍，且r>lr > lr>l”

那么问题就等价于：“是否存在lll和rrr满足r>lr>lr>l且prefix[r]−prefix[l−1]prefix[r] - prefix[l - 1]prefix[r]−prefix[l−1]是kkk的整数倍”

“prefix[r]−prefix[l−1]prefix[r] - prefix[l - 1]prefix[r]−prefix[l−1]是kkk的整数倍”则说明prefix[r]prefix[r]prefix[r]和prefix[l−1]prefix[l - 1]prefix[l−1]关于kkk同余。

等等，同余？

我们直接记录下prefixprefixprefix中每一个元素关于kkk的余数不就好了么

遍历一遍prefixprefixprefix数组，如果prefixprefixprefix中某个元素关于kkk的余数在之前出现过，那么就说明存在prefix[i]prefix[i]prefix[i]和prefix[j]prefix[j]prefix[j]，其中j>ij>ij>i且prefix[i]prefix[i]prefix[i]和prefix[j]prefix[j]prefix[j]关于kkk同余。

但是题目要求是r>lr>lr>l，也就是说需要满足“j>i−1j>i-1j>i−1”，即“j−i≥2j-i\geq 2j−i≥2”

因此，我们将prefix[i]prefix[i]prefix[i]关于kkk的余数，延迟两个元素再插入哈希表中即可。

• 时间复杂度O(n)O(n)O(n)，其中nnn是数组中元素的个数
• 空间复杂度O(n)O(n)O(n)

AC代码

C++

class Solution {
public:bool checkSubarraySum(vector& nums, int k) {int n = nums.size();vector prefix(n + 1, 0);for (int i = 0; i < n; i++) {prefix[i + 1] = prefix[i] + nums[i];}unordered_set se;for (int i = 2; i <= n; i++) {se.insert(prefix[i - 2] % k);if (se.count(prefix[i] % k))return true;}return false;}
};

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127979626