[lv2] 연속 부분 수열 합의 개수

https://school.programmers.co.kr/learn/courses/30/lessons/131701

 

누적합으로 투 포인터에 쓰일 초기 값을 구해준다.

이후 투포인터로 탐색한다.

 

원형 배열이므로, 엔드 포인터가 배열의 끝에 닿으면 0으로 다시 바꿔준다.

 

(입력 값 범위가 작으므로, 일일히 더하는 단순 구현으로도 될 것 같다.)

import java.util.*;

class Solution {
    public int solution(int[] elements) {
        int answer = 0;
        int E = elements.length;

        Set<Integer> set = new HashSet<>();

        // 누적합 : 윈도우 초기 값
        int[] d = new int[E];

        d[0] = elements[0];

        for(int i=1; i<E; i++) {
            d[i] = d[i-1] + elements[i];
        }

        // 투 포인터
        for(int i=0; i<E; i++) {
            int st = 0;
            int ed = i + 1;
            int val = d[i];

            while(st < E) {

                if(ed == E)
                    ed = 0;

                set.add(val);
                val += elements[ed++] - elements[st++];
            }
        }

        return set.size();
    }
}