Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // Created by fpdjsns
- // Copyright © 2019 fpdjsns. All rights reserved.
- //
- /*
- * 시간복잡도 : O(N)
- * 공간복잡도 : O(N)
- */
- #include<iostream>
- #include<vector>
- using namespace std;
- int main() {
- int N, M;
- cin >> N >> M;
- vector<int> subSum(N + 1, 0);
- int tmp;
- for (int i = 1; i <= N; i++){
- cin >> tmp;
- subSum[i] = subSum[i - 1] + tmp;
- }
- int ans = 0;
- int l = 0, r = 1;
- while (l <= N && r <= N) {
- int sum = subSum[r] - subSum[l];
- if (sum == M) {
- int cnt = 1;
- while (r + 1 <= N && subSum[r] == subSum[r + 1]) {
- cnt++; r++;
- }
- while (l + 1 <= N && subSum[l] == subSum[l +1]) {
- cnt++; l++;
- }
- l++; r++;
- ans += cnt;
- }
- else if(sum < M){
- r++;
- }
- else {
- l++;
- }
- }
- cout << ans;
- return 0;
- }
Add Comment
Please, Sign In to add comment