广元网站建设优化,提升网站访问量,wordpress考试模板,wordpress帖子置顶给你一个整数数组 nums 和一个整数 k #xff0c;编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组#xff1a;子数组大小 至少为 2 #xff0c;且子数组元素总和为 k 的倍数。如果存在#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。如果存…给你一个整数数组 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输出false523. 连续的子数组和 - 力扣Leetcode思路定义前缀和 数组 preSum, preSum[ i ] 表示 nums[0, ..., i] 的和若是有子数组 nums[i, ..., j] 和是 k的倍数那么有 ( preSum[j] - preSum[i] ) % k 0 即两者除以k后的余数是相等的。 preSum[j] % k preSum[i] % k。我们定义一个 map, key为当前前缀和的余数即 key preSum[i] % k若是有前缀和preSum[j] % k preSum[i] % k 且 j - i 2 说明存在子数组 nums[i1,..., j] 的和为 k的倍数。这里要考虑一下特殊情况当preSum[i] % k 0 即前缀和nums[0, ..., i] 本身就是 k的倍数若是 i 1 即子数组的长度大于等于 2cclass Solution {
public:vectorint preSum;mapint, vectorint targetMap; // key is preSum[ i ]%k, value is ibool checkSubarraySum(vectorint nums, int k) {preSum vectorint(nums.size(), 0);for(int i 0; i nums.size(); i) {if(i 0) {preSum[i] nums[i];} else {preSum[i] preSum[i-1] nums[i];}int key preSum[i] % k;if(key 0 i1) { // 若是从下标 0 开始的前缀和 preSum[i] 满足是 k的倍数且子数组长度大于2那么题目中要求的子数组我们是可以满足的子数组就是 nums[0, ..., i]return true;}if(targetMap.count(key)) {for(auto v:targetMap[key]) {if(i-v2) {return true;} else {targetMap[key].push_back(i);}}} else {vectorint vec;vec.push_back(i);targetMap[key] vec;}}return false;}
};
