2003번 수들의 합2

문제가 되게 기본적이지만 이런 문제일수록 처음에 생각한 답이 절대 아니다.
일일이 해보면 되는거 아니야? 라고 생각할 수 있지만, 통과할 수 없을 것이다.
이런 기초적인 문제일수록 생각해야 하는 2가지가 있다.
1. 불필요한 작업을 하고 있는가?
2. 중복되는 작업을 하고 있는가?
여기서는 2번에 해당하므로 최대한 시간 복잡도를 줄여야 한다.
일일이 i,j쌍을 찾고 sum을 구하는 것에서 부터 시작하여 lt,rt를 만들어 sum을 더하고 빼면서 시간복잡도를 줄인다.

#include <iostream>
#include <vector>

using namespace std;
int n, m;
int main() {
	//freopen("in1.txt", "rt", stdin);
	int cnt = 0;
	cin >> n >> m;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int lt = 0, rt = 0;
	int sum = arr[0];
	while (rt<n) {
		//cout << "error " <<"rt:"<< rt<< " sum"<<sum<<'\n';
		if (sum == m) {
			cnt++;
			rt++;
			sum += arr[rt];
		}
		else if (sum <m) {
			
			rt++;
			if (rt == n) break;
			sum += arr[rt];
		}
		else if (sum >m) {
			sum -= arr[lt];
			lt++;

		}

	}
	cout << cnt << '\n';
	return 0;
}