https://www.acmicpc.net/problem/2003
만약 2중for문을 통해서 체크를 진행한다면 이 문제의 경우 최대 N이 10000이기때문에 1억ms가 걸린다. -> 이경우 시간초과가 발생가능하다. 그렇기 때문에 투포인터 알고리즘을 통해서 진행하였습니다.
투포인터 알고리즘의 경우 O(N) 의 시간복잡도를 가지기 때문에 시간초과를 피할 수있습니다.
투 포인터 알고리즘
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int list[] = new int[N];
st = new StringTokenizer(br.readLine());
for (int idx = 0; idx < N; idx++) {
list[idx] = Integer.parseInt(st.nextToken());
}
int result = 0;
//M값 체크용
int check_sum = 0;
int start_idx = 0;
int end_idx = 0;
while (start_idx != N) {
if(end_idx == N){
check_sum -= list[start_idx++];
if(check_sum == M)
result+=1;
continue;
}
if(check_sum >= M){
check_sum -= list[start_idx++];
}
else if(check_sum < M){
check_sum += list[end_idx++];
}
if(check_sum == M){
result+=1;
}
}
System.out.println(result);
}
}