[프로그래머스 / JS] 연속부분수열 합의 갯수

으 어렵다..  연속적인 원소를 원하는 만큼 뽑으려면 어떻게 짜야 할까. 뽑아서 더하고 배열에 넣고 new Set() 해서 중복된거 제거하면 될 거 같은데. 다중 for문은 시간복잡도가 너무 커질거 같고..

아! 슬라이딩 윈도우 방법 써보자!

 

function solution(elements) {
    const set = new Set();
    const L = elements.length

    for(let size = 1; size <= L; size++) {
        let right = 0;
        let sum = 0;
        
        for(let left = 0; left < L; left++) {
            if(left === 0) {
                while(right < size) {
                    sum += elements[right++]
                }
            } else {
                sum -= elements[left - 1];
                if(right === L) {
                    right = 0
                }
                sum += elements[right++]
            }
            set.add(sum)
        }
    }
    
    return set.size
}

원형으로 돌다보니까 left, right 변수명이 조금 애매하다. 

그래도 이중 for문 사용해서 시간복잡도 O(N2) 걸린다.