[효율성/투포인터스 알고리즘] 연속 부분 수열1

문제

N개의 수로 이루어진 수열이 주어집니다.
이 수열에서 연속부분수열의 합이 특정숫자 M이 되는 경우가 몇 번 있는지 구하는 프로그램을 작성하세요.
만약 N=8, M=6이고 수열이 다음과 같다면
12131112
합이 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 86 12131112

▣ 출력예제 1 3

---

결과

O

내가 푼 방식

const solution = (array, sum) => {
  const n = array.length
  let answer = 0;
  for(let i = 0; i < n; i++) {
  	let totalSum = array[i];
    for(let k = 0; k < n; k++) {
        totalSum += array[k]
      	if(totalSum === sum) {
          answer++
          break;
        }
      	if(totalSum > sum) break;
    }  
  }
  return answer;
}
solution([1,2,1,3,1,1,1,2],6)

 접근과정

1. 두 번의 반복문을 통해 특정 숫자 m이 되거나 넘는지를 계속 sum하여 판단한다. 

2. 특정 숫자 m이 되면 answer을 증가시켜주고 멈추고 넘을 시 그냥 멈춘다.

3. 더해진 answer값을 리턴한다.

---

모범답안

function solution(m, arr){
    let answer=0, lt=0, 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;
}

리뷰