효율성(투포인터 알고리즘) - 연속 부분수열 2

문제

입력되는 수열에서 연속부분수열의 합이 특정숫자 m 이하가 되는 경우 몇 번 있는가?
만약 m이 5라면
입력예제 1 3 1 2 3에서는
합이 5이하가 되는 연속부분수열은
[1]
[3], [1, 3]
[1], [3, 1], [1, 3, 1]
[2], [1, 2]
[3], [2, 3]로 총 10가지 이다.

입력예제1
1 3 1 2 3

출력예제
10

 

풀이

 

코드

 

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

  for(let rt = 0; rt < arr.length; rt++) {
    sum += arr[rt];
    while (sum > m) sum -= arr[lt++];
    // if (sum <= m) //이거 굳이 안해도 위에 while(sum >m)값의 반대 조건이니까 주석 조건과 같은은 조건을 충족한다.
    answer += rt - lt + 1;
  }
  return answer;
}

console.log(solution(5, [1,3,1,2,3])); // 10
console.log(solution(100, [1,1,1,1,1])); // 15

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의