数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律研究C++ 中的子数组总和等于 K
假设我们有一个整数数组和一个整数 k，我们需要找出总和与 k 相同的所有连续子数组的总数。因此，如果 nums 数组为 [1, 1, 1] 并且 k 为 2，那么输出将为 2。
为了解决这个问题，我们将执行以下步骤−
- 定义一个名为 sums、temp := 0、sums[0] := 1 和 ans := 0 的映射
- 对于 i 在数组的大小的范围内
- temp := temp + n[i]
- 如果 sums 具有 k – temp，则
- ans := ans + sums[k - temp]
- 将 sums[-temp] 的值增加 1
- 返回 ans
示例（C++）
我们来看看以下实现，以获得更好的理解−
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int subarraySum(vector<int>& n, int k) {
unordered_map <int, int> sums;
int temp = 0;
sums[0] = 1;
int ans =0;
for(int i =0;i<n.size();i++){
temp+= n[i];
if(sums.find(k-temp)!=sums.end()){
ans += sums[k-temp];
}
sums[-temp]++;
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {1,1,1};
cout << (ob.subarraySum(v, 2));
}输入
[1,1,1] 2
输出
2
更新日期：2020 年 4 月 29 日
695 次查看
广告