LeetCode刷题实战523：连续的子数组和
共 2169字，需浏览 5分钟
·
2022-02-12 06:14
Given an integer array nums and an integer k, return true if nums has a continuous subarray of size at least two whose elements sum up to a multiple of k, or false otherwise.
An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.
子数组大小 至少为 2 ，且
子数组元素总和为 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
解题
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
int len = nums.size();
if(k < 0)
k = -k;
if(len < 2)
return false;
map<int,int> mp;
mp[0] = -1; // 处理数组和刚好能整除k的情况
int rem = 0;
for(int i = 0;i < len;i++){
rem += nums[i];
if(k) // 避免除数为0
rem = rem % k;
if(mp.find(rem) != mp.end() ){
if(i - mp[rem] > 1)
return true;
}
else
mp[rem] = i;
}
return false;
}
};