数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究C++ 中的连续子数组和
假设我们有一个非负数列表和一个目标整数 k，我们必须编写一个函数来检查数组是否有一个大小至少为 2 的连续子数组，其总和是 k 的倍数，总和等于 n*k，其中 n 也是一个整数。因此，如果输入类似于 [23,2,4,6,7]，并且 k = 6，则结果将为 True，因为 [2,4] 是大小为 2 的连续子数组，并且总和为 6。
为了解决这个问题，我们将按照以下步骤进行操作 −
- 创建一个映射 m，设置 m[0] := -1，sum := 0，n := nums 数组的大小
- 对于 i 在范围 0 到 n – 1 之间
- sum := sum + nums[i]
- 如果 k 为非零，则 sum := sum mod k
- 如果 m 具有 sum，并且 i – m[sum] >= 2，则返回 true
- 如果 m 没有 sum，则设置 m[sum] := i
- 返回 false
让我们看看以下实现以获得更好的理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int, int> m;
m[0] = -1;
int sum = 0;
int n = nums.size();
for(int i = 0; i < n; i++){
sum += nums[i];
if(k)
sum %= k;
if(m.count(sum) && i - m[sum] >= 2){
return true;
}
if(!m.count(sum)) m[sum] = i;
}
return false;
}
};
main(){
vector<int> v = {23,2,4,6,7};
Solution ob;
cout << (ob.checkSubarraySum(v, 6));
}输入
[23,2,4,6,7] 6
输出
1
更新于: 02-2020 年 5 月
1K+ 查看次数
广告