[BOJ][2003] 수들의 합 2

문제 : https://www.acmicpc.net/problem/2003

---

부분합 + 투포인터 로 풀었다.

N개의 수를 입력받으면서 부분합 배열을 만든다.

subSum[i] = i까지 수들의 합.

인덱스 변수 2개를 준비한다. (l, r)

2개의 변수는 부분합의 범위를 구하는데 사용되며 범위는 (l, r] 이다.

범위가 (l, r] 일 때 해당 부분 배열의 합은 subSum[r] - subSum[l] 이 된다.

l, r을 0에서부터 증가시키면서 해당 부분 배열의 합이 M과 같다면 정답이 될 수 있는 경우이다.

합이 M보다 작다면 부분 배열의 합이 더 커져야 하므로 r을 증가시키고

M보다 크다면 합이 더 작아져야 하므로 l을 증가시킨다.

시간복잡도는 O(N).

---

소스코드 : https://gist.github.com/fpdjsns/de452683e1d872f959aecf4b67bc5833