[leetcode][2003] 수들의 합 2 : https://www.acmicpc.net/problem/2003 부분합. 투포인터

수들의 합 2.cpp

//
//  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;
}