[Javascript] 연속 부분수열 1

연속 부분수열 1

N개의 수로 이루어진 수열이 주어집니다.

이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을
작성하세요.

만약 N=8, M=6이고 수열이 다음과 같다면

1 2 1 3 1 1 1 2

합이 6이 되는 연속부분수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지입니다.

입력설명

첫째 줄에 N(1≤N≤100,000), M(1≤M≤100,000,000)이 주어진다.

수열의 원소값은 1,000을 넘지 않는 자연수이다.

출력설명

첫째 줄에 경우의 수를 출력한다.

입력예제1

8 6

1 2 1 3 1 1 1 2

출력예제1

3

풀이 과정

투포인터 알고리즘으로 주어진 수열을 lt와 rt라는 투 포인터를 둘 다 인덱스 0으로 잡아 놓는다.

수열을 돌면서 M값이 작으면 rt값을 더한 후 rt 포인터를 하나 증가시킨다.

M값 보다 sum 값이 더 크면 lt 값을 빼주고 lt 포인터를 하나 증가 시킨다.

rt가 배열의 끝까지 전부 돌면 종료 시키고 카운트 값을 리턴한다.

나의 Solution

function solution(m, arr){
    let answer=0;
    let lt=0;
    let rt=0;
    let sum = 0;

    //while문을 돌면서
    while(rt<arr.length){
      //합이 m이 되면 lt를 빼고 ++ 해주고
        if(sum === m){
            answer++;
            sum -=arr[lt];
            lt++
        } else if(sum > m){
          //sum 값이 더 크면 lt 값을 빼주고 ++
            sum -= arr[lt];
            lt++
        } else{
          //sum이 더 작으면 rt를 더하고 rt++
            sum += arr[rt];
            rt++;
        }
    }
    return answer;
}

다른 Solution

function solution(m, arr){
    let answer=0;
    let lt=0;
    let sum = 0;

  for(let rt=0; rt<arr.length; rt++){
      sum +=arr[rt];
      if(sum===m) answer++;
      while(sum>=m){
          sum-=arr[lt++];
          if(sum===m) answer++
      }
  }
  return answer;
}