사용한 것
- 배열의 i 번째 인덱스 ~ j 번째 인덱스 까지의 합을 효율적으로 구하기 위한 누적합
- O(N)으로 배열의 가능한 구간을 탐색하기 위한 투포인터
풀이 방법
- 입력 값으로 누적합을
sum
에 저장한다.
- 투포인터와
sum
을 사용하여
- 현재 구간의 합이
m
과 같으면 answer
증가, r
증가
- 현재 구간의 합이
m
보다 크면 l
증가
- 현재 구간의 합이
m
보다 작거나 l
과 r
이 같으면 r
증가
코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] sum = new int[n + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
int num = Integer.parseInt(st.nextToken());
sum[i] = sum[i - 1] + num;
}
int answer = 0;
int l = 0;
int r = 1;
while (l < r && r <= n) {
int diff = sum[r] - sum[l];
if (diff == m) {
answer++;
}
if (diff > m) {
l++;
}
if (diff <= m || l == r) {
r++;
}
}
System.out.println(answer);
}
}