[JS] 2Level / 연습문제 / 연속 부분 수열 합의 개수

문제 설명

문제 풀이 방법

• 이번 문제는 슬라이딩 윈도우 알고리즘을 이용한 문제다.
  처음 접한 알고리즘이기에 조금 어려웠다....
  아무리 해답을 봐도 이해가 좀처럼 되지 않았다.......
  서로 비슷한 슬라이딩 윈도우 알고리즘과 투포인터 알고리즘은 조만간 정리해서 글로 작성해 공부하자.
• 우선 중복 되는 값을 처리하기 위해 Set를 만들어 준뒤,
  나누는 수열의 길이는 1부터 주어지는 원소들의 길이와 같기 때문에 1부터 시작해 elements.length 까지 동작.
• 슬라이딩 윈도우 알고리즘의 특징은 기존에 있던 사이즈에서 새롭게 나타나는 부분과
  기존에 있던 부분이 없이지는 점이있다.
  이 문제에서는 숫자들의 합의 경우를 구하는 것이기 때문에 합에서
  이전 합에서 가장 작은 인덱스의 값을 빼고 새로 들어올 인덱스의 값을 더해주며
  슬라이딩 윈도우 알고리즘을 구현한다.

코드 

const solution = (elements) => {
  const set = new Set();
  const length = elements.length;
    
  for (let width = 1; width <= length; width++) {
    let sum = 0;
    for (let st = 0; st < length; st++) {
      if (st === 0) {
        sum = elements.slice(0, width).reduce((acc, cur) => acc + cur, 0);
      }
      else {
        sum -= elements[st - 1];
        sum += elements[(st + width - 1) % length];
      }
      set.add(sum)
    }
  }
  return set.size;
};