Victor’s Research
题意
给定一个长度为 n 的数组 找出有多少子数组的和为 k
思路
先求前缀和数组sum[] 题目要求可以表示为求有多少个r ，l 满足sum[r]−sum[l]==s (l < r)
转换一下可以得到：s u m [ l ] = = s u m [ r ] − s
即求对于当前的 sum[i] i 左边有多少区间和等于sum[i]−s i ∈ [ 1 , n ]
因为求的是 i 左边的区间 所以求完后再记录sum[i] 避免重复
代码
#include <bits/stdc++.h> #define int long long #define INF 0x3f3f3f3f #define mod 1000000007 #define endl '\n' #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); i >= (st);--(i)) using namespace std; typedef long long LL; typedef pair<int, int> PII; inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } const int N = 200009; int n, s; int sum[N]; map<int, int>mp; void solve() { cin >> n >> s; for (int i = 1; i <= n; ++i) { scanf("%lld", &sum[i]); sum[i] += sum[i - 1]; } int res = 0; mp[0] = 1; for (int i = 1; i <= n; ++i) { res += mp[sum[i] - s]; mp[sum[i]]++; } cout << res << endl; } signed main() { //int t; cin >> t; //while (t--) solve(); return 0; }
