[JAVA] 연속 부분수열

문제 유형

연속된 값과 관련되느 투포인터 알고리즘 문제

 

풀이 방법

1.이중 FOR문

시간복잡도 O(N^2) 데이터의 갯수가 늘어날 수록 시간이 엄청 걸린다.

 

2.투포인터 알고리즘

O(N^2)를 O(N)으로 풀 수 있도록 해준다.

 

코드

import java.util.Scanner;

public class Main {
    public int solution(int N, int M, int[] arr) {
        int count = 0;
        int sum = 0;
        int start = 0;

        for (int end=0; end < N; end++ ) {
            sum += arr[end];
            if (sum == M) count++;
            while (sum>=M) {
                sum -= arr[start++];
                if (sum == M) count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr = new int[N];
        int M = in.nextInt();
        for (int i=0; i<N; i++) {
            arr[i] = in.nextInt();
        }
        System.out.println(T.solution(N, M, arr));
    }
}

 

느낀 점

연속된 값과 관련되면 투포인터와 슬라이딩을 기억하자